Do Extra Tapes or Non-Determinism Expand Decidability?

Adding multiple tapes or non-determinism to a Turing machine does not expand the class of decidable problems because a standard single-tape deterministic Turing machine can simulate both models. While these enhancements can make algorithms faster or easier to design, every language that can be decided by a multi-tape or non-deterministic Turing machine can also be decided by a basic single-tape deterministic machine.

Simulating Multiple Tapes on a Single Tape

A \(k\)-tape Turing machine has \(k\) independent tapes and \(k\) read/write heads. At first glance, this seems more powerful than a single-tape machine, which can only read and write at one location at a time. However, a single-tape deterministic Turing machine \(S\) can simulate any \(k\)-tape machine \(M\) by storing the contents of all \(k\) tapes on its single tape.

To do this, \(S\) separates the contents of the \(k\) tapes using a special delimiter symbol, such as \(\#\). To keep track of where each of the \(k\) heads is currently positioned, \(S\) uses marked versions of the tape alphabet symbols (for example, \(\dot{a}\) instead of \(a\)) to indicate that a head is currently scanning that cell.

To simulate a single step of \(M\), the single-tape machine \(S\) performs two main phases:

  1. It scans its tape from left to right to read the \(k\) marked symbols, recording them in its finite control.
  2. It scans back across the tape to update the marked symbols and move the head markers left or right according to \(M\)'s transition function.

If \(M\) runs in \(t(n)\) steps on an input of length \(n\), each tape uses at most \(O(t(n))\) cells. Simulating one step of \(M\) takes \(O(t(n))\) steps on \(S\), resulting in a total simulation time of \(O(t(n)^2)\). Because \(M\) halts on all inputs if it is a decider, \(S\) also halts on all inputs, proving that both models decide the exact same class of languages.

Simulating Non-Determinism Deterministically

A non-deterministic Turing machine (NTM) can have multiple possible transitions from a single configuration, forming a computation tree where each branch represents a different sequence of choices. An NTM accepts an input if at least one branch reaches an accept state, and it decides a language if it halts on all branches for every input.

A deterministic Turing machine (DTM) can simulate an NTM by searching this computation tree. However, a naive depth-first search (DFS) can fail: if the DTM explores an infinite branch first, it will loop forever and never discover an accepting branch elsewhere in the tree.

Instead, the DTM uses a breadth-first search (BFS) strategy:

  • It systematically explores all computation paths of length \(1\), then all paths of length \(2\), then length \(3\), and so on.
  • It can do this by using a deterministic tape to enumerate sequences of non-deterministic choices (for example, strings over \(\{1, 2, \dots, b\}\), where \(b\) is the maximum branching factor) in lexicographical order.
  • For each sequence, the DTM simulates the NTM from the start state along that specific path.

If the NTM has an accepting branch at depth \(d\), the DTM is guaranteed to reach it in finite time and accept. If the NTM halts and rejects on all branches, the DTM will eventually exhaust all finite paths and reject.

Complexity vs. Decidability

The key takeaway is the distinction between computability (what can be decided) and complexity (how fast it can be decided). Simulating multiple tapes introduces a polynomial slowdown, and simulating non-determinism introduces an exponential slowdown of \(2^{O(t(n))}\). While these slowdowns are central to open questions in complexity theory like \(\text{P}\) versus \(\text{NP}\), they do not affect decidability. As long as a simulation halts in a finite number of steps, the class of decidable problems remains unchanged.