Nondeterministic Turing Machines

A deterministic Turing machine's transition function has signature

mapping each (state, tape symbol) pair to exactly one action. A nondeterministic Turing machine relaxes this to

where $\mathcal{P}(\cdot)$ denotes the power set. At each step, the machine may have zero, one, or many legal moves available, and it is free to take any of them. There is no mechanism actually resolving the choice — the model simply asserts all choices are pursued "in parallel" in the mathematical sense. This turns a computation from a single sequence of configurations into a computation tree: the root is the start configuration on the given input, and each configuration has one child for every move the transition function permits from it. A branch that reaches a configuration with no available moves is a dead branch (analogous to explicit rejection). An NTM $N$ accepts an input string $w$ if at least one path from the root reaches a configuration in an accepting state — even if every other branch rejects, loops, or dies. $N$ rejects $w$ if every branch is finite and every leaf is rejecting (no branch loops forever and none accepts). If some branches loop forever and none accepts, $N$ itself does not halt on $w$, mirroring the same three-way outcome (accept / reject / loop) that ordinary Multitape Turing Machines exhibit. It is essential to separate two distinct questions that nondeterminism raises: what languages can NTMs recognize or decide (a question of computability, answered completely in this article), and how fast can they do it compared to deterministic machines (a question of complexity, only foreshadowed here). The equivalence theorem below settles the first question unconditionally: NTMs and DTMs recognize exactly the same class of languages, and decide exactly the same class of decidable languages. The efficiency question is subtler and is precisely the origin of the P versus NP problem, which builds on the very simulation technique developed here.

The equivalence proof is constructive: given any NTM $N$, we build a DTM $D$ that simulates $N$ and decides/recognizes the same language. The key design decision is how to explore the computation tree.

Why depth-first fails. A naive simulator might pick a branch, follow it to completion (accept, reject, or forever), then backtrack and try the next branch — a depth-first traversal. This is unsound: if the tree has an infinite branch (the machine loops on some sequence of choices) positioned before a shallow accepting leaf in the traversal order, the simulator gets stuck exploring the infinite branch and never reaches the accepting one, even though $N$ does accept $w$.

The fix: breadth-first search. Instead, the simulator explores the tree level by level: all configurations reachable in 1 step, then all reachable in 2 steps, and so on. Since accepting configurations, if they exist at all, occur at some finite depth $d$ along some branch, a breadth-first search is guaranteed to discover one after enumerating finitely many configurations — regardless of what happens in other, possibly infinite, branches. To make this concrete on an ordinary (multitape, hence by known equivalence single-tape) deterministic machine, we use a three-tape simulator:

• Tape 1 holds the input $w$, untouched throughout.
• Tape 2 is the simulation workspace, where $D$ writes out the tape contents of the NTM configuration currently being explored.
• Tape 3 holds an address string over the alphabet $\{1, 2, \dots, b\}$, where $b$ is the maximum branching factor of $N$'s transition function. This string names a path from the root: symbol $i$ at position $k$ means "at depth $k$, take the $i$-th nondeterministic choice available."

$D$ generates address strings in a fixed enumeration order (numeric order: $\varepsilon, 1, 2, \dots, b, 11, 12, \dots$) — the standard technique used later when discussing Encodings and Enumerators for systematically listing objects. For each address string, $D$ resets tape 2 to the input, then replays the moves the address dictates, one node of the tree per prefix, checking after each move whether that choice was even legal (some addresses correspond to no real branch, since not every configuration has $b$ children) and whether the resulting configuration accepts. ``` Algorithm SIMULATE-NTM(N, w): // N: an NTM with transition function δ, max branching factor b // w: input string // D: the deterministic simulator we are describing Tape 1 := w // never modified Tape 3 := empty string // will enumerate addresses in {1..b} loop forever: copy Tape 1 onto Tape 2 // reset simulated tape to input set simulated configuration C := start configuration of N on w address := next string in {1,...,b} in counting order // ε,1,2,...,b,11,... write address onto Tape 3 for each symbol s in address (left to right): if C has no legal moves (dead branch): break out of this for-loop, discard this address, continue outer loop if s > (number of legal moves available at C): break out of this for-loop, discard this address, continue outer loop // this address does not correspond to a real path C := result of applying the s-th legal move of δ to C (update Tape 2 and simulated state/head position accordingly) if C is an accepting configuration: ACCEPT // (finished replaying the whole address without accepting or dying) // do nothing special; just move on to the next address in the enumeration ``` If $N$ is a decider (every branch of every input halts), $D$ can be strengthened into a decider too: since the tree is then finite, $D$ can detect when every address up to a certain length has been exhausted with no accept found, and safely reject. If $N$ merely recognizes a language (some branches may loop), $D$ recognizes the same language but may itself loop forever on rejected inputs — which is unavoidable, since recognizability, not decidability, is all that is preserved in general.

Notice in the figure that a depth-first explorer that happened to descend into the "infinite branch" subtree before trying node 6 would never terminate, while the breadth-first order guarantees node 6 (the accept) is visited at a finite, bounded step regardless of what lurks deeper in sibling subtrees.

Correctness argument. We must show $L(D) = L(N)$ where $L(\cdot)$ denotes the language recognized. ($\Rightarrow$) If $D$ accepts $w$, then $N$ accepts $w$. $D$ only enters its ACCEPT state after correctly replaying a legal sequence of moves of $N$ from the start configuration to a configuration in an accepting state of $N$. Each step of the replay was checked against $\delta$ for legality, so this sequence is a genuine root-to-leaf path in $N$'s computation tree ending in acceptance. Hence $N$ accepts $w$ by definition. ($\Leftarrow$) If $N$ accepts $w$, then $D$ accepts $w$. Since $N$ accepts $w$, some finite path of moves $m_1, m_2, \dots, m_k$ (each $m_i$ a legal choice at its configuration) leads from the start configuration to an accepting configuration. Let $a$ be the address string encoding this exact sequence of choices, using $b$ as the alphabet size (each $m_i$ corresponds to some choice-index between $1$ and the branching factor at that node, which is at most $b$). Since $D$'s enumeration of addresses in counting order eventually produces every finite string over $\{1,\dots,b\}$, it will eventually produce $a$ itself, replay it faithfully (by the same legality argument as above, applied in reverse), and detect the accepting configuration, entering ACCEPT. This is an if-and-only-if correspondence between accepting computations of $N$ and accepting runs of $D$'s simulation loop, which is exactly the invariant needed: $D$ enters ACCEPT on input $w$ if and only if some branch of $N$'s tree on $w$ accepts. The breadth-first-flavored counting order is what makes the "$\Leftarrow$" direction actually terminate in finite time rather than merely being true in an infinite limit — this is precisely why depth-first traversal, which can defer the correct finite-length address indefinitely, is unsound while a fair (breadth-first-equivalent) enumeration is sound.

Decider case. If $N$ is guaranteed to halt on every branch for every input (a decider), the tree on input $w$ is finite (König's lemma: a finitely branching tree with only finite paths is itself finite). $D$ can be modified to perform an explicit level-by-level breadth-first search — generating exactly the addresses of length $0, 1, 2, \dots$ up to the point where every branch at that depth is finished (either a leaf or dead) — and reject once no accepting configuration remains reachable at any further depth. This gives a genuine decider $D$, matching $N$'s decidability rather than merely its recognizability.

Time and space complexity. Let $N$ run in time $t(n)$ on inputs of length $n$, meaning every branch of $N$'s computation tree on any length-$n$ input has depth at most $t(n)$, and let $b$ be the maximum branching factor. The tree has at most

nodes. $D$'s breadth-first simulator must potentially visit all of them, and replaying each address from the root costs $O(t(n))$ time (to copy the input and step through the address), so the total simulation time is

an exponential blowup in the running time even though $t(n)$ itself might be small (even polynomial). This exponential gap is not a defect of this particular simulation strategy — no fundamentally faster general simulation is known, and closing this gap for polynomial-time bounded computations is exactly the content of the P versus NP question. Space usage is more modest: tape 2 needs only $O(t(n))$ cells (the simulated tape cannot grow faster than the number of steps taken), and tape 3 needs $O(t(n))$ cells to hold one address, so the simulator's space is polynomial in $t(n)$ even though its time is exponential — an asymmetry worth remembering.

Tradeoffs, honestly stated. The equivalence theorem is unconditional and constructive: every NTM can be replaced by a DTM deciding or recognizing exactly the same language, with no restriction on the NTM's structure. What is not preserved, in general, is efficiency: there is no known way to simulate an NTM by a DTM with only polynomial slowdown, and it is a major open problem whether one exists. So "NTMs add no computational power" is a precise, correct, and complete statement about decidability and recognizability, but it says nothing reassuring about running time, a distinction every student should hold onto tightly.

Consider a toy NTM $N$ deciding whether a binary string $w$ contains the substring `101`, using nondeterminism merely for illustration (this language is of course also easy deterministically — the point is to trace the simulation machinery, not to need nondeterminism). $N$ works as follows: at each tape cell, before reading it, $N$ nondeterministically guesses whether the substring `101` starts here. If it guesses "yes," it deterministically checks the next three symbols; if they match `101`, it accepts; otherwise this branch dies. If it guesses "no," it moves the head one cell right and repeats the guess. If the head runs off the end of the input without any branch having accepted, that branch rejects. So at every non-dead-end configuration, $N$ has (up to) two choices: guess `1` (try to match here) or guess `2` (skip and continue). The branching factor is $b = 2$. Run $N$ on $w = 0110100$ (length 7). Let's trace the accepting path and see how the address-string simulator finds it.

The shortest accepting path is: at position 0 choose "2" (skip), then at position 1 choose "1" (attempt, matches). Encoded as an address string over $\{1,2\}$ this is $a = 21$. The deterministic simulator $D$ enumerates addresses in counting order: $\varepsilon, 1, 2, 11, 12, 21, 22, 111, \dots$. Tracing $D$'s outer loop:

$D$ accepts at address `21`, the sixth address in the enumeration — confirming both that acceptance is found, and that it is found in a small, finite number of steps despite the existence of other addresses (like ones probing positions 5, 6) whose branches simply die rather than loop. In this example nothing loops forever, but the reason $D$'s strategy is safe in general — as argued in Complexity & correctness — is that no matter how many other branches were infinite instead of merely dead, the shallow accepting address `21` would still be reached at the same finite point in the counting-order enumeration.

The nondeterministic Turing machine crystallized as a formal object during the 1960s and 1970s, as researchers systematized the Turing-machine framework Alan Turing had introduced decades earlier and began classifying problems not just by decidability but by resource cost.

Nondeterministic Turing machines are, first and foremost, a conceptual scaffold: almost no real hardware "runs" nondeterministically in the Turing-machine sense, since physical computers must make one choice at a time. Their importance is that they crisply formalize the "guess-and-verify" pattern that pervades algorithm design and complexity theory. The class NP is literally defined as the languages decided by NTMs running in polynomial time, and the question of whether every such guess can be found as fast as it can be verified — P versus NP — is arguably the central open problem of theoretical computer science. Beyond that headline connection, nondeterministic models are the backbone of automata theory taught alongside Turing machines: nondeterministic finite automata and nondeterministic pushdown automata use the identical subset-construction or tree-search ideas to prove equivalence with their deterministic counterparts, and NPDAs (unlike NTMs) genuinely add expressive power over deterministic PDAs, making the contrast instructive. In practice, tools like SAT solvers, constraint solvers, regular-expression engines, and parser generators are engineering answers to "how do we efficiently emulate nondeterministic search on deterministic hardware," directly inheriting the breadth-first-versus-depth-first tension this article develops. The equivalence proof's technique — encode a choice sequence as a string, enumerate all such strings systematically — is also the direct ancestor of the enumeration and encoding tricks used when discussing Encodings and Enumerators, and the entire discussion presumes the robustness that the Church-Turing Thesis asserts: any reasonable notion of "effective procedure," deterministic or not, computes the same class of functions.

Ask the tutor: How does the breadth-first simulation change if we want the resulting deterministic machine to also be a decider, not just a recognizer?