Nondeterminism
A nondeterministic machine may branch into many possible next steps at once and accepts if any branch leads to acceptance.
The model
A deterministic machine has exactly one next move per configuration. A nondeterministic machine may have several, and it accepts an input if some sequence of choices leads to an accepting state. Think of it as guessing the right move at every fork, or equivalently exploring all forks in parallel.
Guess and check
Nondeterminism is best understood as a two-phase process: guess a certificate, then deterministically verify it. This is exactly the verifier view of NP. The machine's power comes from always guessing correctly when a correct guess exists.
It does not add computability
For plain computability, nondeterminism changes nothing: a nondeterministic Turing machine computes the same functions as a deterministic one, by simulating all branches through systematic search. It only affects how efficiently, in the resource sense, a problem can be described.
Where it does matter: complexity
Simulating a nondeterministic machine deterministically may cost exponential time, since the tree of choices can double at each step. Whether that blowup is avoidable is precisely the P vs NP question. For finite automata, by contrast, nondeterminism can be removed with only a state blowup, no change in language class.
Two readings of a branch
- Existential: accept if any branch accepts (defines NP)
- Universal: accept if all branches accept (defines co-NP)
- Mixing the two by alternation defines the polynomial hierarchy
Why it is a useful fiction
No physical machine is nondeterministic in this sense, but the concept is a clean way to define classes and to express "a solution exists that is easy to check." It turns hard search problems into tidy definitions, which is why it anchors so much of complexity theory.