The GATE Grind

GATE 2022 CS – Question 46

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple select

Which of the following is/are undecidable?

  1. Given two Turing machines $M_1$ and $M_2$, decide if $L(M_1)=L(M_2)$.
  2. Given a Turing machine $M$, decide if $L(M)$ is regular.
  3. Given a Turing machine $M$, decide if $M$ accepts all strings.
  4. Given a Turing machine $M$, decide if $M$ takes more than 1073 steps on every string.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Given two Turing machines $M_1$ and $M_2$, decide if $L(M_1)=L(M_2)$.; (B) Given a Turing machine $M$, decide if $L(M)$ is regular.; (C) Given a Turing machine $M$, decide if $M$ accepts all strings.

Explanation

Answer: A, B, C.

More Turing Machines and Undecidability questions

All Turing Machines and Undecidability questions →