A single tape Turing Machine M has two states q0 and q1, of which q0 is the…
2003
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
0 1 B q0 q1, 1, R q1, 1, R Halt q1 q1, 1, R q0, 1, L q0, B, LThe 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 tape 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 string ending in a 0
- D.
M halts on all string ending in a 1
Attempted by 10 students.
Show answer & explanation
Correct answer: A
The Turing machine M transitions from q0 to q1 on reading 0 or 1, writing 1 and moving right. From state q1, on reading 1 it stays in q1 and moves right; on reading 0 it transitions to q0, writes 1, and moves left. On encountering B in state q1, it transitions to q0 and moves left. Since the machine only halts when reading B in state q0, it will halt only after processing all input symbols and reaching the blank symbol. For any non-empty string in (0+1)+, M will continue moving right and never reach a halt state because it only halts when reading B in q0, which occurs after the input ends. Therefore, M does not halt on any string in (0+1)+.