Nondeterministic Turing machine

A Nondeterministic Turing machine differs from a deterministic Turing machine because its transition relation may provide several legal next moves rather than exactly one. A move can change the finite control state, write a tape symbol, and move the head left or right; the machine therefore generates a computation tree instead of a single computation sequence.¹

The machine accepts an input if at least one branch halts in an accepting state, while it rejects if no branch accepts. A branch that runs forever does not by itself establish acceptance. This existential interpretation is the defining convention: the machine is imagined to select a successful sequence of choices whenever one exists, not to sample choices according to probabilities. The model can use one or several tapes without changing the class of languages it recognizes.

Nondeterministic and deterministic Turing machines have the same computability power, even though their running times can differ greatly. A deterministic machine can simulate a nondeterministic one by systematically exploring its computation tree, for example through breadth-first or depth-first search, while recording configurations to avoid losing unfinished branches.²

That simulation may require exponential time when the nondeterministic machine has many branching choices, so nondeterminism is chiefly a resource distinction in complexity theory rather than a stronger notion of what can be computed. For decidable languages, every accepting branch can be checked as a finite certificate; for recognizable languages, an accepting branch may exist even when all rejecting branches or nonhalting behavior prevent a decision procedure.

The polynomial-time nondeterministic Turing machines define the class NP: a language belongs to NP when some such machine accepts every yes-instance within a polynomial bound, and rejects all branches for every no-instance within that bound.² This formulation is equivalent to the verifier view, in which a deterministic polynomial-time algorithm checks a polynomial-length certificate.

The distinction between deterministic polynomial time and NP underlies the P versus NP problem. The Cook–Levin theorem showed that Boolean satisfiability is NP-complete, meaning that every language in NP can be reduced to it by a polynomial-time transformation.³ Nondeterministic machines also define broader classes, such as NPSPACE, although space complexity behaves differently because configurations and reused space can be explored without storing the entire computation tree.

Nondeterministic computation has several less obvious interpretations beyond the familiar “guess and verify” picture. A branching machine can be viewed as accepting when its computation tree contains a witness path, making the model closely related to existential quantification in logic and to reachability in a directed graph of configurations.

The same idea supports formal descriptions of nondeterministic finite automata and pushdown automata, although those models have different memory limits and language powers. In complexity theory, reversing the acceptance condition from “some branch” to “every branch” leads to universal computation and helps motivate the class co-NP. Alternation generalizes both existential and universal branching, and polynomial-time alternating computation provides a framework connecting logical quantifiers with complexity classes. These extensions show why nondeterminism is a structural concept, not merely an informal shortcut for guessing.

Configuration

A complete description of a machine's current state, tape contents, and head positions.

Computation tree

The branching tree whose nodes are configurations and whose edges represent legal transitions.

NP

The class of decision problems accepted by a nondeterministic Turing machine in polynomial time.

Certificate

A finite witness that a deterministic polynomial-time verifier can check for a yes-instance.

NP-complete

A problem class containing problems in NP to which every NP problem can be reduced in polynomial time.