nondeterminism

Imagine you are walking through a maze and you reach a fork in the path. A deterministic walker must commit to exactly one direction. A nondeterministic walker, by contrast, is allowed to split into copies and send one copy down each branch at once; if any single copy eventually reaches the exit, we say the maze was solved. Nondeterminism is exactly this idea of being allowed to follow several possibilities at the same time instead of just one.

More precisely, in a deterministic machine each situation (where you are, what you read) leads to exactly one next move. In a nondeterministic machine a situation may allow several next moves, or even none at all. The machine is said to succeed if there exists at least one sequence of legal moves that ends in success. There is no requirement that every path succeed, and no requirement that a path even exist for every situation — one good path is enough. A useful slogan is: a nondeterministic device accepts when SOME choice works.

The single most important and surprising fact about nondeterminism in finite automata is that it adds no extra power: anything a nondeterministic finite automaton can do, an ordinary deterministic one can also do (we just may need many more states). So here nondeterminism is a convenience for the designer, not a new kind of computing. Be careful: nondeterminism is NOT randomness and NOT something a real chip does for free. It is a mathematical and descriptive device. This same idea returns much later, far more consequentially, with the class NP — where whether the convenience can always be removed cheaply is the famous open question.