The GATE Grind

GATE 2014 CS (CS2) – Question 45

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

Let $\langle M\rangle$ encode a Turing machine over {0,1}. Let $L=\{\langle M\rangle:M\text{ accepts a string of length }2014\}$. L is ______.

  1. decidable and recursively enumerable
  2. undecidable but recursively enumerable
  3. undecidable and not recursively enumerable
  4. decidable but not recursively enumerable

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) undecidable but recursively enumerable

Explanation

Dovetail simulations of the finitely many binary strings of length2014 and accept if any simulation accepts, proving recursive enumerability. The property is a nontrivial semantic property of the recognised language, so Rice’s theorem makes it undecidable. Hence **B**. Finitely many inputs do not guarantee their simulations halt.