Unary notation, although cumbersome for practical computations, is very
convenient for programming Turing machines. The resulting programs are much
shorter and simpler than if we had used another representation, such as binary or
decimal.
Adding numbers is one of the fundamental operations of any computer, one
that plays a part in the synthesis of more complicated instructions. Other basic
operations are copying strings and simple comparisons. These can also be done
easily on a Turing machine.
Example 9.10
Design a Turing machine that copies strings of 1’s. More precisely, find a
machine that performs the computation
for any w ∈{1} + .
To solve the problem, we implement the following intuitive process:
1. Replace every 1 by an x.
2. Find the rightmost x and replace it with 1.
3. Travel to the right end of the current nonblank region and create a 1 there.
4. Repeat Steps 2 and 3 until there are no more x's.
The solution is shown in the transition graph in Figure 9.7. It may be a little hard
to see at first that the solution is correct, so let us trace the program with the
simple string 11. The computation performed in this case is
Figure 9.7