nondeterministiset

Nondeterministiset (English: nondeterministic) describe computational models in which, from a given configuration, several different next steps are possible. A computation is considered accepting if at least one of the possible paths leads to an accepting state. This contrasts with deterministic models, where the next state is uniquely determined by the current state and input. Nondeterminism is a theoretical abstraction used to understand decision problems and computational complexity, rather than a description of physical machines.

In automata theory, nondeterministic finite automata (NFA) can have multiple transitions for a given input symbol, and may include epsilon transitions that consume no input. NFAs recognize the same class of languages as deterministic finite automata (DFAs): the regular languages. Any NFA can be converted to an equivalent DFA through the subset construction, though the resulting DFA may have exponentially more states in the worst case.

Nondeterministic Turing machines (NTMs) extend the idea to general computation. An NTM may have several possible actions from a given configuration, and a computation accepts if at least one branch halts in an accepting state. NTMs are central to the complexity class NP, defined as the set of problems solvable in polynomial time by an NTM. Equivalently, NP is the set of problems whose solutions can be verified in polynomial time by a deterministic Turing machine.

The concept of nondeterminism is distinct from probabilistic randomness. In practice, physical devices are deterministic or use randomness or parallelism to mimic nondeterministic behavior. In theory, nondeterminism provides a useful framework for formulating and analyzing complexity, language recognition, and computational limits.