For questions 3 to 5, remember that a Turing machine starts in state 1, reading the leftmost nonblank cell.
1. Given the Turing machine instruction
(1,1,0,2,L)
and the configuration
... b 1 0 b ... (Tape read head is in state 1, and is over symbol 1 on the left)
Draw the next configuration.
2. A Turing machine contains only the following instructions:
(1,1,1,1,R)
(1,b,1,2,R)
Can this machine ever reach the following configuration? Explain your answer.
... b 0 1 b ... (Tape read head is in state 1, and is over symbol 1 on the left)
3. Find the output for the Turing machine
(1,1,1,2,R)
(1,0,0,2,R)
(1,b,1,2,R)
(2,0,0,2,R)
(2,1,0,1,R)
when run on the tape
... b 1 0 0 1 b ...
4. Find the output for the Turing machine
(1,1,1,2,L)
(2,b,0,3,L)
(3,b,1,4,R)
(4,0,1,4,R)
when run on the tape
... b 1 b ...
5. Describe the behavior of the Turing machine
(1,1,1,1,R)
(1,0,0,2,L)
(2,1,0,2,L)
(2,b,1,3,L)
(3,b,b,1,R)
when run on the tape
... b 1 0 1 b ...