GATE CSE 2003 | Question: 53

Question

A single tape Turing Machine $M$ has two states $q0$ and $q1$, of which $q0$ is the starting state. The tape alphabet of $M$ is $\{0, 1, B\}$ and its input alphabet is $\{0, 1\}$. The symbol $B$ is the blank symbol used to indicate end of an input string. The transition function of $M$ is described in the following table.

$$\begin{array}{|l|l|l|l|}\hline \text{}  &  \text{$0$} & \text{$1$} & \text{$B$} \\\hline \text{$q0$}  &  \text{$q1, 1, R$} & \text{$q1, 1, R$} & \text{$Halt$} \\\hline \text{$q1$}  &  \text{$q1, 1, R$} & \text{$q0, 1, L$} & \text{$q0, B, L$} \\\hline  \end{array}$$

The table is interpreted as illustrated below.

The entry $(q1, 1, R)$ in row $q0$ and column $1$ signifies that if $M$ is in state $q0$ and reads $1$ on the current page square, then it writes $1$ on the same tape square, moves its tape head one position to the right and transitions to state $q1$.

Which of the following statements is true about $M$?

• A. $M$ does not halt on any string in $(0+1)^+$
• B. $M$ does not halt on any string in $(00+1)^*$
• C. $M$ halts on all strings ending in a $0$
• D. $M$ halts on all strings ending in a $1$

Comments

but turing machine does not accept epsilon

---

When a Tm goes to a dead state i.e no transition mentioned then Is this TM halt?

---

but turing machine does not accept epsilon

From where students get to learn these type of wrong concepts ?

Anyway, the correct concept is below :

A TM can accept Epsilon.

The problem of “Whether a given TM accepts epsilon or not”  is Undecidable, BUT it doesn’t mean that A TM cannot accept epsilon.

For example, The problem of “Whether a given TM computes product of two integers or not”  is Undecidable, BUT it doesn’t mean that A TM cannot compute product of integers.

---

Thanks @Deepak Poonia sir.

Answer 1

Option A is correct because M doesn't halts on any string in (0+1)+.

Option B is incorrect because M halts when the input string is Epsilon. When the i/p alphabet is Epsilon the tape alphabet will be B. When state q0 encounters B, M halts. 

Option C and D are incorrect because M never halts on strings ending with either 0 or 1.