Variations on Turing Machines

Simulating a 2-track tape with a standard Turing machine

The Turing machine that adds binary numbers allows pairs of bits as input symbols. Another way to look at this example is as a machine with a $2$-track tape. See the tape in the diagram below.

We’ll design a $\text{TM}$ that adds these numbers together, column-wise as before, leaving the tape with the following contents: the sum in the bottom track and the top track all blank.

We’ll show that a standard, 1-track $\text{TM}$ can simulate a 2-track machine by introducing new symbols to stand for pairs of symbols, as follows:

With these substitutions, the initial configuration in the figure above appears on a 1-track tape as $$ ...