Variations on Turing Machines
Discover how standard Turing machines can simulate more complex variations, including multitape and multitrack machines, by introducing new symbol systems and tape structures. Learn the methods used to replicate multiple tapes on single-track tapes, the concept of independent read/write heads, and how these simulations relate to the Church-Turing Thesis. This lesson provides foundational knowledge of advanced Turing machine models and their equivalences.
We'll cover the following...
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 -track tape. See the tape in the diagram below.
We’ll design a 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 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 ...