GATE CS 2003 Q53 — Undecidability

To determine the behavior of the Turing Machine $M$, let us trace its execution on simple non-empty input strings:

Case 1: Input string is "0" (Tape: $\underline{0}\ B$ with head at $0$ in state $q_0$)

1. $(q_0, 0) \to$ writes $1$, moves $R$, transitions to $q_1$. Tape: $1\ \underline{B}$, state $q_1$.
2. $(q_1, B) \to$ writes $B$, moves $L$, transitions to $q_0$. Tape: $\underline{1}\ B$, state $q_0$.
3. $(q_0, 1) \to$ writes $1$, moves $R$, transitions to $q_1$. Tape: $1\ \underline{B}$, state $q_1$.

Steps 2 and 3 repeat indefinitely. Thus, $M$ does not halt on "0".

Case 2: Input string is "1" (Tape: $\underline{1}\ B$ with head at $1$ in state $q_0$)

1. $(q_0, 1) \to$ writes $1$, moves $R$, transitions to $q_1$. Tape: $1\ \underline{B}$, state $q_1$.
2. $(q_1, B) \to$ writes $B$, moves $L$, transitions to $q_0$. Tape: $\underline{1}\ B$, state $q_0$.

This also results in an infinite loop.

General Analysis:

• If $M$ encounters a $1$ in state $q_1$, it writes $1$, moves left, and transitions to $q_0$. In state $q_0$, it reads that same $1$, writes $1$, moves right, and transitions back to $q_1$. This creates an immediate infinite loop between these two adjacent cells.
• If $M$ reaches the end of the input string (blank symbol $B$) in state $q_1$, it writes $B$, moves left, and transitions to $q_0$ (where it reads $1$). From $q_0$ reading $1$, it moves right to $B$ in state $q_1$, creating an infinite loop at the boundary.

Thus, $M$ never halts on any non-empty string, meaning it does not halt on any string in $(0+1)^+$. Note that $M$ halts on the empty string $\epsilon$ (since $\delta(q_0, B) = \text{Halt}$), which belongs to $(00+1)^*$, making option B false.