Question 45

Language Specification:

Undecidability (Rice's Theorem):

• The property $P = \{ L(M) \mid L(M) \cap \{0, 1\}^{2014} \ne \emptyset \}$ depends purely on the language recognized by $M$, not its syntactic encoding (semantic property).
• Non-triviality:
  • There exists a TM $M_1$ with $L(M_1) = \Sigma^*$ (accepts strings of length 2014), so $\langle M_1 \rangle \in L$.
  • There exists a TM $M_0$ with $L(M_0) = \emptyset$ (accepts nothing), so $\langle M_0 \rangle \notin L$.
• By Rice's theorem, $L$ is undecidable.

Recursive Enumerability (Turing Recognizability):

• The set of strings of length 2014 is finite (exactly $2^{2014}$ strings).
• We can construct an enumerator / recognizer $M'$ that dovetails the execution of $M$ on all $2^{2014}$ candidate strings in parallel (step 1 for all strings, step 2 for all strings, and so on).
• If $M$ accepts at least one string of length 2014, the simulation will halt and accept in finite steps.
• If $M$ accepts none, the simulation runs indefinitely.
• Thus, $L$ is semi-decidable (recursively enumerable).

Conclusion:
$L$ is undecidable but recursively enumerable, which is option (B).