22
for class on Thursday April 23, 1998
Please read Sections 10.5 and 10.6 of the Schneider and Gersting text, and be prepared to discuss the following:
1. Figure out how a Turing machine might 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 1's (that's 2 times 3)
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 replace input 1's 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 take 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?