GATE CSE 2022 Q46: Which Turing machine problems are undecidable

Which of the following is/are undecidable?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B, C (official GATE 2022 final answer key)

Concept used: Rice's theorem covers non-trivial properties of $L(M)$ ; a bounded number of steps can be checked by simulation.

First step: For (D), note that within 1073 steps $M$ can read at most the first 1073 symbols, so only finitely many inputs need simulating.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key