mittedeterministlik

Mittedeterministlik is a term used in Estonian mathematics and computer science to describe systems whose future state is not uniquely determined by their current state and input. In such models, a given situation may lead to several possible next states, and no single outcome is guaranteed.

In formal language theory, nondeterminism is formalized by nondeterministic finite automata (NFA). An NFA may transition to any of multiple states on the same input symbol and may use epsilon-moves that consume no input. A word is accepted if there exists at least one path through the automaton that consumes the input and ends in an accepting state. A deterministic counterpart, the DFA, has at most one transition for every state and input symbol.

In computational complexity, nondeterminism is modeled by nondeterministic Turing machines. The class NP comprises languages decidable by an NTM in polynomial time, where the machine accepts if there exists some computational path that yields acceptance within the resource bound. Although nondeterminism is a powerful theoretical concept, a nondeterministic computation can be simulated by a deterministic machine, often with an exponential increase in resources in the worst case.

In practice, apparent nondeterminism often reflects concurrency, parallelism, or incomplete information, rather than an intrinsic multiple-future property of a single execution. Distinctions between nondeterministic and probabilistic models are important: nondeterminism does not assign probabilities to outcomes, while probabilistic models explicitly do.

The term is formed from mitte, meaning "not," and determinantlik from the word determinant, reflecting its negation of determinism in Estonian. See also nondeterministic automata, NP, and epsilon-moves.