Project ForgeWhich of the following is/are undecidable?
(A) Given two Turing machines M1 and M2, decide if L(M1) = L(M2). (B) Given a Turing machine M, decide if L(M) is regular. (C) Given a Turing machine M, decide if M accepts all strings. (D) Given a Turing machine M, decide if M takes more than 1073 steps on every string.
- Given two Turing machines M1 and M2, decide if L(M1) = L(M2).
- Given a Turing machine M, decide if L(M) is regular.
- Given a Turing machine M, decide if M accepts all strings.
- DGiven a Turing machine M, decide if M takes more than 1073 steps on every string.
Explanation
(A), (B), and (C) are all non-trivial semantic properties of L(M) (equivalence, regularity, universality) — by Rice's theorem, every such property is undecidable. (D) is actually DECIDABLE: if M takes ≤1073 steps on SOME string, that string can have length at most 1073 (it can't read further input than the number of steps taken), so checking 'does M take >1073 steps on every string' reduces to a FINITE search — simulate M for 1073 steps on every one of the finitely many strings of length ≤1073, and if none halt within that bound, the answer is yes. This bounded simulation always terminates, making (D) decidable.
Source: GATE CS 2022 (2022)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.