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
**(A) Undecidable.** Equivalence of two Turing machines' languages ($L(M_1)=L(M_2)$) is undecidable (reduction from the emptiness problem).
**(B) Undecidable.** "Is $L(M)$ regular?" is a non-trivial property of the language, so Rice's theorem applies.
**(C) Undecidable.** "Does $M$ accept all strings?" ($L(M)=\Sigma^*$) is also a non-trivial property of the language: Rice's theorem.
**(D) Decidable.** "Does $M$ take more than 1073 steps on every string?" only depends on the first 1073 steps. If $M$ takes at most 1073 steps on some input, it reads at most the first 1073 symbols of it. So simulate $M$ for 1073 steps on each of the finitely many inputs of length up to 1073 and check.
Answer: A, B, C.
More Turing Machines and Undecidability questions
GATE 2021 CS (CS1) Q22– Let M denote an encoding of an automaton M. Suppose that = \0,1\. Which of the following…
GATE 2021 CS (CS1) Q49– For a Turing machine M, M denotes an encoding of M. Consider the following two languages.…
GATE 2020 CS Q36– Which of the following languages are undecidable? Note that M indicates encoding of the…
GATE 2019 CS Q44– Consider the following sets: S1. Set of all recursively enumerable languages over the…
GATE 2018 CS Q17– The set of all recursively enumerable languages is
GATE 2018 CS Q46– Consider the following problems. L(G) denotes the language generated by a grammar G. L(M)…