A onto the end of the string of
As on the tape.
This is interpreted as adding 1 to the number on the tape.
A Turing Machine to add two adjacent numbers is implemented by replacing
the space between them with an A, and deleting an A
from the start (or end) of the string of As.
| When we are in state | And the input is | Move to this state | And perform this action |
|---|---|---|---|
| S | A | S | Write blank |
| S | Blank | S1 | Move right |
| S1 | A | S1 | Move right |
| S1 | Blank | H | Write A |