| Data | ||
|---|---|---|
| State | A | ' ' |
| S | S Move right | H Write A |
If the tape contains AA, with the head starting on the
first A, what does this program do?
Positive integers can be represented by strings of A's, where
the number of A's is the number we represented.
For example, the string A represents the number 1, the string
AA the number 2, and so on.
With this interpretation of tape symbols, what does the Turing Machine above
do?
Using this way of representing integers, write a Turing machine program to add two positive integers. Assume that the representations of the two integers are separated on the tape by a single blank and that the machine starts out looking at the first symbol of the first number. At the end of the program the tape must contain the representation of the sum of the two input integers.