Explore BrainMass
Share

Turing machine configurations and outputs

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com October 24, 2018, 11:25 pm ad1c9bdddf
https://brainmass.com/computer-science/theoretical-computer-science/turing-machine-configurations-outputs-193075

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
See Also This Related BrainMass Solution

Turing machines and PDP networks

1. Given what you read about Turing machines and PDP networks, what is one main feature that these systems have in common?
Also, what is one main difference between these two types of systems?

View Full Posting Details