22

### Reading Assignment and Discussion Topics

Computer Science 111

*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.