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

PYQ GATE 2014

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 150 students.

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…