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

Equivalence, regularity and universality of TM languages are undecidable by Rice's theorem and reductions. Option D is decidable by simulating M for at most 1073 steps on the finitely many relevant inputs.