Nondeterministic Turing Machine

A nondeterministic Turing machine (NTM) is a theoretical model of computation in which the machine may follow multiple computational paths simultaneously, accepting an input if any path reaches an accepting state. Unlike a deterministic Turing machine, which has exactly one next state for every configuration, an NTM branches — and this branching is what gives the model its power to define NP and other complexity classes based on existential quantification. The NTM is not a physical proposal; it is a mathematical abstraction that formalizes the idea of guessing correctly.

The NTM is often misunderstood as a model of parallelism, but the equivalence is misleading. Parallel computation distributes work across processors; nondeterminism distributes work across possible worlds, only one of which needs to succeed. A closer analogy is to quantum computing, where superposition permits simultaneous exploration of paths — but quantum measurement collapses superposition irreversibly, whereas nondeterministic acceptance is a clean OR of all branches. Whether this distinction matters for the physical realizability of nondeterministic complexity classes remains unresolved.