Share
Explore BrainMass

Turing machine configurations and outputs

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 ...

Attachments

Solution Preview

1. Next configuration will look like

... b 0 0 b ...

with tape read head pointing to first blank before non-blank symbols above, and state changed to 2.
Tape read head is indicated by vertical arrow in the question with the state mentioned underneath that.

2. Since initial configuration of turing machine starts in state 1 with tape read head placed at the leftmost non-blank symbol, to reach the given state turing machine will have to execute some instructions.

There is no instruction given that ...

Solution Summary

Solution gives detailed explanations for question 2 and 5.

$2.19