EXAMPLE $9\mathrm{.}14$

Design a Turing machine that multiplies two positive integers in

unary notation.

A multiplication machine can be constructed by combining the

ideas we encountered in adding and copying. Let us assume that the

initial and final tape contents are to be as indicated in Figure $9\mathrm{.}10.$

The process of multiplication can then be visualized as a repeated

copying of the multiplicand $y$ for each $1$ in the multiplier $x,$ whereby

the string $y$ is added the appropriate number of times to the partially

computed product. The following pseudocode shows the main steps of

the process.

Repeat the following steps until $x$ contains no more $1\text{'}$s$.$

Find a $1$ in $x$ and replace it with another symbol $a.$

Replace the leftmost $0$ by $0y.$

Replace all $a\text{'}$s with $1\text{'}$s$.$

Although this pseudpcade is sketchy, the idea is simple enough that

there should be no doubt that it can be done.