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

Correct Option: A

Or only epsilon is leading to a halting state as tape contain B as the first character.

Comments

yes you are right

 

---

input alphabet is just {0,1}

---

I think Halt would be a correct choice of a word here. Cause there is no transition defined at Epsilon. So, you can’t say it will get accepted.

https://cs.stackexchange.com/questions/150128/the-difference-between-halting-and-accepting-in-a-turing-machine-in-this-context#:~:text=A%20Turing%20Machine%20halts%20if,halting%20but%20not%20vice%20versa.

Answer 2

Whenever B is given as a input, turing machine halts. This implies epsilon is only accepted when B occurs as an input. 
In positive closure, epsilon is not present. So, Turing machine never halts in case of (0+1)⁺.
 
Thus, option (A) is correct. 
 

Answer 3

this is correct

 

M does not halt on any string in (0+1)+

try it by make turing machine

this is true because oo11, 11 no halt will  be there

try it.

a option is correct

Answer 4

Construct TM with given table and see Epslon is accepted by Machine.

Now Option A,B,C are wrong bcoz all these options are contradictory. 

Epslon is in $(0+1)^{*}$

Epslon is not ending with 0.

Epslon is not ending with 1.

Hence, A is answer here!!