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 …
