22
for class on Thursday April 20, 2000
Please read Sections 10.5 and 10.6 of the Schneider and Gersting text, and be prepared to discuss the following:
1. How might a Turing machine multiply two unary numbers, using the unary copy machine from the last class? Suppose your starting tape looks like this:
. . . b b b A 1 1 B 1 1 1 A b b b . . .
Then your machine should write six ones (that's 2 times 3 ones)
to the right of the rightmost A.
Please note that this convention for unary numbers
is slightly different from the textbook's: the book
represents a non-negative integer n
by a series of (n + 1) ones,
but here we'll use just n ones. As before, you will probably want some
additional "marker" symbols to keep track of input ones you've already processed.
If this is difficult for you, try the "pseudo-code" approach: just
write down in words the simple steps you would perform to do this yourself,
assuming you could only keep one symbol in your head at a time.
2. When you hand-simulate the operation of a Turing machine, you are following some algorithm, of course. Do you think that this algorithm could itself be expressed as a Turing machine? That is, could one Turing machine imitate another? How? In thinking about this question, imagine that the description of the machine being imitated is written on the tape before the imitator starts.