Let \(\langle M \rangle\) be the encoding of a Turing machine as a string over…

GATE · 2014 · CS · Set 2 · Computer Science & IT

Let ⟨M⟩\langle M \rangle be the encoding of a Turing machine as a string over Σ={0,1}Σ = \{0,1\}. Let 

L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}.L=\left\{\langle M \rangle \mid M \text{ is a Turing machine that accepts a string of length 2014} \right\}.

Then LL is:

  1. A.

    decidable and recursively enumerable

  2. B.

    undecidable but recursively enumerable

  3. C.

    undecidable and not recursively enumerable

  4. D.

    decidable but not recursively enumerable

Attempted by 120 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…