Let \(\langle M \rangle\) be the encoding of a Turing machine as a string over…
2014
Let \(\langle M \rangle\) be the encoding of a Turing machine as a string over \(Σ = \{0,1\}\). Let
\(L=\left\{\langle M \rangle \mid M \text{ is a Turing machine that accepts a string of length 2014} \right\}.\)
Then \(L\) is:
- A.
decidable and recursively enumerable
- B.
undecidable but recursively enumerable
- C.
undecidable and not recursively enumerable
- D.
decidable but not recursively enumerable
Attempted by 71 students.
Show answer & explanation
Correct answer: B
Key insight: membership asks whether a given Turing machine accepts at least one string from a fixed finite set (all strings of length 2014). This makes the language semidecidable, but not decidable.
Why it is recursively enumerable (semi-decidable):
There are finitely many strings of length 2014 (2^2014 many). For a given machine M, run M on all these strings in dovetailed fashion (simulate one step on each input in rounds).
If any simulation accepts, the dovetailing will eventually reach that accepting configuration, so we can accept <M>. If none accept we never halt. Thus the language is recursively enumerable.
Why it is undecidable:
Reduce the acceptance (or halting) problem to this problem. Given an instance of the undecidable acceptance/halting problem (a machine N and input w), construct a machine M' that behaves as follows on inputs of length 2014: if the input equals a fixed chosen string s of length 2014, M' simulates N on w and accepts iff N accepts w; for any other length-2014 input, M' immediately rejects.
Then M' accepts some string of length 2014 iff N accepts w. Thus deciding whether a machine accepts some length-2014 string would decide the original undecidable problem. Therefore the language is undecidable.
Conclusion: the language is recursively enumerable but not decidable.
A video solution is available for this question — log in and enroll to watch it.