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).
"nondeterminism." A Dictionary of Computing. . Encyclopedia.com. (March 15, 2019). https://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/nondeterminism
"nondeterminism." A Dictionary of Computing. . Retrieved March 15, 2019 from Encyclopedia.com: https://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/nondeterminism