Turing Machine Equivalences

1. Multi-Tape Turing Machines

Let's start by imagining a Turing Machine with multiple tapes, say $k$ tapes, each with its own independent read/write head. The machine has a single finite control (a single set of states) that reads all $k$ symbols under the heads simultaneously and, based on its current state, decides on the next state, what to write on each of the $k$ tapes, and how to move each of the $k$ heads.

The transition function for such a $k$-tape TM would look like this:
$\delta :Q\times {\Gamma }^k\to Q\times {\Gamma }^k\times \{L,R,S{\}}^k$

For many tasks, this is a much more convenient model. Consider the language $L=\{a^n{b}^n{c}^n\}$. With a 3-tape TM, you could:

1. Copy the input from tape 1 to tape 2.
2. Scan the a's on tape 1, the b's on tape 2, and the c's on tape 1 again, moving all three heads simultaneously to ensure the counts match.

This feels much more direct than the single-tape "marking and shuttling" approach. But does this convenience translate to more power? Can a multi-tape TM recognize a language that a single-tape TM cannot? The answer is no.

Proving Equivalence: Simulating Multiple Tapes on One

We can prove that for any multi-tape TM, there exists an equivalent single-tape TM that recognizes the same language. The proof is a proof by construction: we show how to build a single-tape TM, let's call it S, that simulates any given $k$-tape TM, M.

The core idea is to represent the state of all $k$ tapes on a single tape. To understand how this works, let's start with an intuitive video explanation.

As the video explained, the simulation works by cleverly encoding all the necessary information on one tape. Here's a more formal breakdown of the simulation strategy.

1. Tape Representation:
We can represent the $k$ tapes of M on the single tape of S by concatenating their contents, separated by a special delimiter symbol, like #. To keep track of the head positions, we expand the tape alphabet Γ. For every symbol a in Γ, we add a "marked" version ȧ. A marked symbol ȧ on the tape of S indicates that the corresponding head of M is currently scanning that cell.

2. Simulating a Single Move of M:
To simulate one move of the multi-tape machine M, the single-tape machine S must perform a sequence of operations:

• First Pass (Read): S scans its entire tape from the beginning to find all $k$ marked symbols. As it finds each one, it stores the symbol in its finite control. After this pass, S knows the current state and all the symbols under M's heads.
• Determine Action: Using the information it just gathered, S consults the transition function of M (which is hardcoded into the logic of S) to determine the new state, the new symbols to write, and the direction to move each of the $k$ heads.
• Second Pass (Write & Move): S makes another pass across its tape. When it finds a marked symbol, it updates it with the new symbol and "moves" the mark one position left or right by un-marking the current symbol and marking the adjacent one.
• Tape Management: If a mark needs to move right onto a # symbol, it means that one of M's heads has moved onto a blank cell. S must then shift the entire rest of the tape one position to the right to insert a blank symbol (⊔) for that virtual tape before placing the mark.

Since we have a general algorithm to simulate any move of any $k$-tape TM, we have shown that single-tape TMs are just as powerful. The simulation is much slower, but it recognizes the exact same set of languages.

2. Two-Way Infinite Tape Turing Machines

Another common variation is a Turing Machine whose tape is infinite in both directions. The head starts at some designated cell (cell 0), and can move infinitely to the left or right.

Does this extra "room" to the left add any computational power? Once again, the answer is no.

Proving Equivalence: The "Folding" Technique

We can simulate a two-way infinite tape TM M using a standard single-tape, semi-infinite TM S. The technique is to "fold" the two-way tape at cell 0 and store it on two "tracks" on the single tape.

For a deeper, more formal look at both multi-tape and two-way infinite tape simulations, the following reading is excellent.

As explained in the reading, the simulation works as follows:

• Tape Representation: The single tape of S is treated as having two tracks.
  • Top Track: Stores the cells of M's tape with non-negative indices (0, 1, 2, ...).
  • Bottom Track: Stores the cells of M's tape with negative indices (-1, -2, -3, ...) in reverse order. So, tape cell -1 of M is at index 0 of S's bottom track, cell -2 is at index 1, and so on.
• Simulating a Move: The finite control of S remembers whether it's simulating the head on the positive or negative part of M's tape.
  • If M's head is on a non-negative cell and moves Right, S moves its head Right on the top track.
  • If M's head is on a negative cell (say, -i) and moves Left (to -i-1), S moves its head Right on the bottom track.
  • If M's head is on a negative cell and moves Right, S moves its head Left on the bottom track.
  • Crossing the "fold" (e.g., from cell 0 to -1) involves S simply switching its attention from the top track to the bottom track at its current position (index 0).

This construction proves that a standard TM can simulate a two-way infinite tape TM, meaning they are computationally equivalent.

Conclusion

Today we've established a critical property of Turing Machines: their robustness. Enhancements that seem powerful, like adding multiple tapes or an infinitely long left side of the tape, are ultimately just conveniences. They can make designing TMs easier and often much more efficient, but they do not expand the class of languages that can be recognized. This principle is fundamental to computer science.

Key Takeaways:

• Equivalence through Simulation: We prove that two models of computation are equivalent by showing that one can simulate the other. We've done this for multi-tape and two-way infinite tape TMs.
• Robustness of the TM Model: The fact that these variations don't add power is strong evidence for the Church-Turing Thesis—the claim that any function that can be intuitively "computed" can be computed by a Turing Machine. Many different proposed models of computation have been shown to be equivalent to the TM.
• Power vs. Efficiency: While not more powerful, variant TMs are often more efficient. Simulating a T(n)-time multi-tape TM on a single-tape TM might take O(T(n)^2) time. This distinction between what can be computed and how efficiently it can be computed is the central theme of computational complexity theory, which we will touch on later in the course.

Preview of the Next Lesson:
We've explored adding tapes and space. What about adding a different capability: nondeterminism? In our study of finite automata, we saw that Nondeterministic Finite Automata (NFAs) were equivalent in power to DFAs. In our next lesson, we will define Nondeterministic Turing Machines (NTMs) and ask the same question: are they equivalent to deterministic TMs? The answer will be "yes," but the simulation will be our most intricate one yet.