GATE CS 2016 Set 2 Q44 — Turing Machines

To determine whether the languages $L_1$, $L_2$, and $L_3$ are recursive (decidable), we analyze each one individually:

1. Analysis of $L_1$ and $L_2$

For any Turing machine $M$, in $2016$ steps, the read-write head can scan at most $2016$ cells of the input tape. Consequently, any input symbols beyond the first $2016$ positions cannot influence the computation of $M$ within the first $2016$ steps.

• Let $\Sigma$ be the input alphabet of $M$. The number of possible input prefixes of length at most $2016$ is finite (specifically, $\sum_{i=0}^{2016} |\Sigma|^i$).
• To decide $L_1$ or $L_2$, a decider can simulate $M$ on each of these finitely many inputs for at most $2016$ steps.

• For $L_1$: If $M$ takes $\ge 2016$ steps on at least one of these finite inputs, the decider accepts. Otherwise, it rejects. Since the simulation is guaranteed to terminate in a finite number of steps, $L_1$ is recursive.
• For $L_2$: If $M$ takes $\ge 2016$ steps on all of these finite inputs, the decider accepts. Otherwise, it rejects. Since this simulation also always terminates, $L_2$ is recursive.

2. Analysis of $L_3$

$L_3 = \{\langle M \rangle \mid M \text{ accepts } \epsilon\}$ is the acceptance problem for the empty string.

• The property "accepts $\epsilon$" is a non-trivial semantic property of recursively enumerable languages (some Turing machines accept $\epsilon$, while others do not).
• By Rice's Theorem, any non-trivial semantic property of Turing machines is undecidable. Thus, $L_3$ is not recursive (it is recursively enumerable but not recursive).

Hence, $L_1$ and $L_2$ are recursive, and $L_3$ is not recursive.