Nondeterministic
In computer science, a system is considered nondeterministic if, at some point during its evolution, there are multiple valid paths it can take in a single step, or (more strictly), multiple valid final outputs. Nondeterminism literally means lacking determinism. Determinism in this context refers to the execution path being determined from the initial conditions. A system (e.g. a program) evolves deterministically if, at every point in the execution, only one possible execution path can (and therefore must) be taken.
Consider a language where there are some functions. Multiple function calls can be joined together using OR. In this hypothetical language, this code:
a() OR b()
Will either run a() or b() but not both. One might consider running this program, at which point they must determine which function to run. Which should run? This system is underspecified and nondeterministic, either path can be taken, either function could be run.
This type of nondeterminism is similar to a branch, consider:
if c a() else b()
This has the same property that only a() or b() will run, but it is deterministic, since there is only one possible path to take due to the variable c determining which path to take.
While nondeterminism is as simple as multiple valid paths could be taken at some point(s) in a program, nondeterminism often contextually refers to specific execution styles.
In decidability theory, a nondeterministic branch will go down (one of) the path(s) which will eventually lead to an ACCEPT state. This can be used in computational complexity theory to create algorithms which generate solutions for problems, which may then be verified. In general, nondeterministic automata will take the eventually succeeding path when given the option. Equivalently, a nondeterministic automaton will ACCEPT if any of its execution paths eventually ACCEPT.
In formal language theory, nondeterministic rule derivation results in all possible derivations being applied to a string in parallel, generating a multitude of valid options. The language of a grammar is nondeterministically derived from a starting string by applying every valid combination of derivations on every valid partial derivation, then pruning all derivations which are not made up of solely terminals. Or in the case of (semi-)Thue systems, pruning all derivations which could be further derived.
In lambda calculus and other functional calculi, expressions often have multiple valid reductions at any given step. This means that evaluation is nondeterministic if there is no strategy. Specifying an valuation order results in deterministic evaluation. Even so, many forms of reduction have deterministic outputs in their closure (when considering normal forms). That is, while there are many paths that beta reduction can go through on a given term, all of the ones which result in a normal form will result in the same normal form. This is the Church-Rosser theorem. A system with nondeterministic evaluation but deterministic outputs is called confluent.
Evaluation
Evaluating a nondeterministic system is not straightforward. Since there are multiple valid options, there needs to be some strategy to determine which one(s) to take.
The option that formal grammars take, and the option that a deterministic implementation of a nondeterministic automata must, is to evaluate all possible paths in parallel. We can run a universal program which runs our nondeterministic program. The universal program has a collection of states, which correspond to executions of the nondeterministic program. It steps each of its stored states one after the other in a loop. When a state encounters a nondeterministic choice, the universal program copies the state, such that each new state will go down a different possible path on the next step. This is a form of universal search.
Other execution styles take just one possible path at each juncture.
Stochastic or probabalistic execution is a popular choice within esolangs, with languages like Thue using it, despite otherwise being a faithful formal grammar language. With stochastic execution, a single option is chosen at random.
Precedence is another popular choice, with most regular expression implementations using it. If each possibility is ranked or ordered, then the first valid option can always be taken. This is how most regex implementations determine which option in an alternation to match. While (a)|(a) could have either side match on the string a, most implementations will have the first group/left match.
Other potential options could include:
- Ordering each option and picking a particular index every time
- Ordering each option and picking an index by corresponding it with the next symbol of input