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
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, L |
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 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 (00 + 1)* B) M halts on all string ending in a 0 C) M halts on all string ending in a 1 D) M does not halt on any string in {0,1}+
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
