21
for class on Tuesday April 18, 2000
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.
There are, of course, several approaches to this problem.
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 keep track of where you are in the input.
When your Turing machine halts it should have erased all trace of the markers; some schemes do this "clean-up" at the end, and some do it as they copy.