GATE CS 2014 Set 2 Q35 — Undecidability

To determine the classification of the language $L = \{\langle M \rangle \mid M \text{ is a Turing machine that accepts a string of length 2014}\}$, we analyze its decidability and recursive enumerability.

1. Undecidability (using Rice's Theorem)

Let $P$ be the property of the language recognized by a Turing machine $M$ defined as: $$\text{Property } P: L(M) \text{ contains at least one string of length 2014.}$$

• Semantic Property: This property depends only on the language $L(M)$ recognized by $M$, not on the structure or description of $M$. If $L(M_1) = L(M_2)$, then $M_1$ satisfies $P$ if and only if $M_2$ satisfies $P$.
• Non-triviality:
  • There exists a TM $M_{\text{yes}}$ that accepts all strings (i.e., $L(M_{\text{yes}}) = \Sigma^*$), which contains strings of length 2014. Thus, $\langle M_{\text{yes}} \rangle \in L$.
  • There exists a TM $M_{\text{no}}$ that rejects all strings (i.e., $L(M_{\text{no}}) = \emptyset$), which contains no strings of length 2014. Thus, $\langle M_{\text{no}} \rangle \notin L$.

Since $P$ is a non-trivial semantic property of recursively enumerable languages, by Rice's Theorem, the language $L$ is undecidable.

2. Recursive Enumerability (RE)

A language is recursively enumerable if there exists a Turing machine that halts and accepts for every string in the language. We can construct a recognizer $U$ for $L$ as follows:

1. Given input $\langle M \rangle$, generate all strings of length 2014 over $\Sigma = \{0, 1\}$. There are exactly $2^{2014}$ such strings (a finite set). Let this set be $S = \{w_1, w_2, \dots, w_k\}$, where $k = 2^{2014}$.
2. Run $M$ on all strings in $S$ in parallel using dovetailing (interleaving steps):
   • For step $s = 1, 2, 3, \dots$:
     • Run $M$ on each $w_i \in S$ for $s$ steps.
     • If $M$ accepts any $w_i$ within $s$ steps, halt and accept.

If $M$ accepts at least one string of length 2014, the recognizer $U$ will eventually find it in a finite number of steps and halt. If $M$ does not accept any such string, $U$ will run forever. Thus, $L$ is recursively enumerable.

Therefore, $L$ is undecidable but recursively enumerable.