A mode of computation in which, at certain points, there is a
choice of ways to proceed: the computation may be thought of as choosing
arbitrarily between them, or as splitting into separate copies and pursuing all
choices simultaneously. The precise form of nondeterminism depends on the
particular computational formalism. For example, a nondeterministic Turing
machine will have a choice of moves to make for a given internal state and tape
symbol being read.
After a choice has been made, other choice-points will be
encountered. There is therefore a tree of possible different overall
computations, with the nonterminal nodes representing choice-points. If, for
example, the algorithm performs some kind of "search",
then the search succeeds if at least one sequence of choices (path through the
tree) is successful. Many algorithms are expressed most conveniently in this
way; nondeterminism also arises naturally in connection with concurrency. Nondeterminism is important in the field of complexity: it is believed that a
nondeterministic Turing machine is capable of performing in "reasonable lime"
computations that could not be so performed by any deterministic Turing machine.