Turing machine configurations and outputs
Not what you're looking for?
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 ...
Purchase this Solution
Solution Summary
Solution gives detailed explanations for question 2 and 5.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Javscript Basics
Quiz on basics of javascript programming language.
Word 2010: Tables
Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.