21
for class on Tuesday April 21, 1998
Please read Sections 10.1 through 10.4 of the Schneider and Gersting text, and be prepared to discuss the following:
Turing machines are an amazingly simple yet powerful model of computation, and will be the subject of three classes. In this class we will explore the basics of Turing machines, and design a number of very simple ones. Please figure out a Turing machine program for the simple problem of copying a string of 1's. Suppose the tape originally looks like this:
. . . b b b b B 1 1 1 1 1 1 A b b b b b b b . . .
where the little b's stand for blanks. Your machine should
make a copy of the 1's and put them to the right of the A, so
when your machine halts, the tape should look like this:
. . . b b b b B 1 1 1 1 1 1 A 1 1 1 1 1 1 b b b . . .
Your machine should start at the big B (the
left-most nonblank symbol), and it should work
for any number of 1's, not just the example shown above.
The general idea should be to find a 1 in the input, then
move right until a blank is found and replace it with a 1,
then move left to the next input 1, and so on.
You will probably want to use some "marker" symbol
like X or Y
to replace 1's you have already copied and do not want to copy again.
Then at the end of your copy you should change the markers
back into 1's.