Simulating NTMs with Multi-tape DTMs

1. The Challenge: How to Systematically Explore a Tree

The core of the proof is a simulation. We need to build a DTM that can take any NTM and an input string w and faithfully reproduce the NTM's computation. Since the DTM is deterministic, it can only follow one path at a time. The challenge, therefore, is to devise a strategy for this single-path machine to explore the entire, potentially infinite, computation tree of the NTM.

The key is that the DTM must find an accepting configuration if one exists, without getting lost. Your background in algorithms will immediately bring two primary tree traversal strategies to mind: Depth-First Search (DFS) and Breadth-First Search (BFS).

• Why not DFS? A depth-first search would explore one branch of the NTM's computation tree to its conclusion before backtracking. The problem is that a branch might be infinite (the NTM could loop). If the DTM chose to explore an infinite branch, it would never halt and never get to explore other branches, potentially missing an accepting configuration on a shorter, finite branch.

• Why BFS? A breadth-first search explores the tree level by level. It checks all computation paths of length 1, then all paths of length 2, then length 3, and so on. This approach guarantees that if an accepting configuration exists at any finite depth d in the tree, the BFS will find it. It is a complete search strategy for this problem.

2. The Simulator: A 3-Tape Deterministic Turing Machine

To implement this BFS strategy, we will design a multi-tape DTM. While the simulation can be done on a standard single-tape TM, using a multi-tape model makes the construction much clearer. As we proved in a previous lesson, any multi-tape DTM has an equivalent single-tape DTM, so this does not affect the validity of our proof.

Our simulator DTM, let's call it D, will use three tapes to simulate the NTM, N.

Here's the role of each tape:

1. Tape 1 (Input Tape): This tape holds the original input string w and is never modified. It serves as a permanent reference.
2. Tape 2 (Simulation Tape): This is the main work tape. Before simulating a new branch of N's computation, D copies the input from Tape 1 to this tape. It then performs the simulation of that specific branch on this tape.
3. Tape 3 (Address Tape): This tape is the "brains" of the BFS. It stores a string that represents a specific path in N's computation tree. For example, if the maximum number of choices at any step in N is b, we can use an alphabet ${\Sigma }_b=\{1,2,...,b\}$. The string 213 on the address tape would mean: "take the 2nd choice at the first step, the 1st choice at the second step, and the 3rd choice at the third step."

3. The Simulation Algorithm

The DTM D will systematically generate all possible address strings on Tape 3 in a breadth-first manner (i.e., by increasing length: $ϵ$, 1, 2, ..., 11, 12, ...) and simulate the corresponding path.

Here is the algorithm for D operating on an input w:

1. Initialization: Tape 1 contains w. Tapes 2 and 3 are empty.
2. Outer Loop (Path Generation):
   a. Place the next path address string (in lexicographical order) on Tape 3. Start with the empty string, then '1', '2', etc.
3. Inner Loop (Path Simulation):
   a. Copy the content of Tape 1 (w) to Tape 2.
   b. Simulate the NTM N on Tape 2. At each step, if a nondeterministic choice is required, consult the next symbol on Tape 3 to decide which transition to take.
   c. After using a symbol from Tape 3, move the head on Tape 3 to the right.
4. Check Outcome:
   a. If the simulation on Tape 2 reaches N's accept state, then D accepts and halts immediately. The proof is complete for this input.
   b. If the simulation on Tape 2 halts in a reject state, or if the path on Tape 3 is invalid (e.g., it specifies choice '3' when only two are available), or if the address string on Tape 3 runs out, this computation branch is finished. D then proceeds to the next path.
5. Repeat: Erase Tapes 2 and 3. Go back to step 2 to generate the next path address.

If the NTM N accepts w, there is at least one finite path to an accept state. The DTM D will eventually generate the address for this path on Tape 3, simulate it, and accept. If N loops or rejects on all paths, D will never find an accepting state and will either run forever (correctly simulating N's looping behavior) or exhaust all finite paths and reject (if N is a decider).

To see this entire process explained with clear visuals, the following video provides an excellent walkthrough.

4. An Alternative View: Nondeterminism as Advice

There's another elegant way to conceptualize this simulation, which is particularly useful for understanding complexity theory later on. We can think of an NTM as a DTM that gets help in the form of an "advice string."

Imagine a deterministic TM with two read-only input tapes: one for the user's input w, and another for an "advice string" x. At every step where the original NTM had a choice, this new DTM consumes a symbol from the advice string x to tell it which path to take.

From this viewpoint:

• An NTM N accepts w if there exists an advice string x such that the corresponding DTM accepts the pair (w, x).

The simulation then becomes a deterministic search for a "correct" advice string. The simulating DTM simply tries all possible advice strings—$ϵ$, 1, 2, 11, 12, etc.—in increasing order of length, simulating the "advised" DTM for each one. This method, often called dovetailing, is another implementation of the same BFS principle.

Conclusion

Today, we have formally proven one of the fundamental theorems of computability theory: nondeterminism does not add computational power to a Turing Machine.

Key Takeaways:

• Equivalence: For every Nondeterministic Turing Machine, there is an equivalent Deterministic Turing Machine that recognizes the same language. This means NTMs and DTMs are equivalent in their language-recognizing ability.
• Proof by Simulation: The proof is constructive. It shows how to build a DTM (usually a 3-tape one) that simulates the NTM.
• BFS is Key: The simulation relies on a breadth-first search of the NTM's computation tree to ensure that any existing accepting path will eventually be found.
• Cost of Simulation: While the DTM can simulate the NTM, the simulation may be exponentially slower. If an NTM accepts a string in t steps, the simulating DTM might take time exponential in t to find the accepting path. This difference in efficiency is the foundation of the P vs. NP problem, which we will explore later.

Preview of the Next Lesson:
We've seen that one TM can simulate another. This leads to a profound idea: could there be one single, "master" TM that can simulate any TM, given its description? The answer is yes, and it's called the Universal Turing Machine (UTM). The UTM is the theoretical precursor to the modern stored-program computer, which can run any program (a "description" of a machine) you give it. We will explore its definition and significance in our next lesson.