Nondeterminism Definition/Meaning:

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.

Near by Terms: No-Address Instruction Node Noise Noiseless Coding Noisy Mode NOMAD Nonbinary Logic Nondestructive Read-Out (NDRO) Nondeterminism Nonequivalence Gate Nonequivalence Operation Nonhierarchical cluster Analysis Nonimpact Printer Nonlinear Equations Nonlinear Regression Model Nonmemoiy Reference Instruction Non Parametric Techniques Nonprecmptive Allocation Nonprocedural Language Nonsingular Matrix Nonterminal Node Nonvolatile Memory Non Von Neumann Architecture Nonreturn to Zero (NRZ) No-Op Instruction (pass instruction; do-nothing instruction) NOR Gate Normal Distribution (Gaussian distribution) Normal Form