nondeterminism
nondeterminism 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 model of computation.
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 whose paths are all possible different computations, and whose nonterminal nodes represent 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.
Nondeterministic constructs in programming languages can offer a choice of control, e.g. do S1 or S2 od
or a choice of data, e.g. y := ? and y := x.R(x);
These latter select a value for y randomly and such that it satisfies test R. Many algorithms are expressed most conveniently using such constructs; nondeterminism also arises naturally in connection with interleaving and concurrency.
Nondeterminism is important in the field of complexity: it is believed that a nondeterministic Turing machine is capable of performing in “reasonable time” computations that could not be so performed by any deterministic Turing machine (see P=NP question).
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 whose paths are all possible different computations, and whose nonterminal nodes represent 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.
Nondeterministic constructs in programming languages can offer a choice of control, e.g. do S1 or S2 od
or a choice of data, e.g. y := ? and y := x.R(x);
These latter select a value for y randomly and such that it satisfies test R. Many algorithms are expressed most conveniently using such constructs; nondeterminism also arises naturally in connection with interleaving and concurrency.
Nondeterminism is important in the field of complexity: it is believed that a nondeterministic Turing machine is capable of performing in “reasonable time” computations that could not be so performed by any deterministic Turing machine (see P=NP question).
More From encyclopedia.com
Choice , Choice
The act of the will that is concerned with means to an end; as such, it is distinct from the act of deliberation that precedes it and from the… Sociometry , The term “sociometry” has several meanings, but historically the closest association is with the work of J. L. Moreno, particularly his analysis of i… Konrad Zuse , Zuse, Konrad
ZUSE, KONRAD
d. Hünfeld, Germany, 18 December 1995), logic, computers, programming, computer industry.
Zuse is popularly recognized in G… Turing Machine , British mathematician Alan Turing (1912–1954) described what became known as the "Turing Machine" in his 1936 paper, "On Computable Numbers, with an… Computer Science , The term Computer Science encompasses three different types of research areas: computability, efficiency, and methodology.
General Introduction
Compu… Parallel Processing , Parallel processing is information processing that uses more than one computer processor simultaneously to perform work on a problem. This should not…
You Might Also Like
NEARBY TERMS
nondeterminism