Incomputer science, adeterministic algorithm is analgorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.
Formally, a deterministic algorithm computes amathematical function; a function has a unique value for any input in itsdomain, and the algorithm is a process that produces this particular value as output.
Deterministic algorithms can be defined in terms of astate machine: astate describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in itsinitial state orstart state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result.
Examples of particularabstract machines which are deterministic include thedeterministic Turing machine anddeterministic finite automaton.
A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:
Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, mostprogramming languages and especiallyfunctional programming languages make an effort to prevent the above events from happening except under controlled conditions.
The prevalence ofmulti-core processors has resulted in a surge of interest in determinism in parallel programming and challenges of non-determinism have been well documented.[1][2] A number of tools to help deal with the challenges have been proposed[3][4][5][6] to deal withdeadlocks andrace conditions.
It is advantageous, in some cases, for a program to exhibit nondeterministic behavior. The behavior of a card shuffling program used in a game ofblackjack, for example, should not be predictable by players — even if the source code of the program is visible. The use of apseudorandom number generator is often not sufficient to ensure that players are unable to predict the outcome of a shuffle. A clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold 'em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.[7] These problems can be avoided, in part, through the use of acryptographically secure pseudo-random number generator, but it is still necessary for an unpredictablerandom seed to be used to initialize the generator. For this purpose, a source of nondeterminism is required, such as that provided by ahardware random number generator.
Note that a negative answer to theP=NP problem would not imply that programs with nondeterministic output are theoretically more powerful than those with deterministic output. The complexity classNP (complexity) can be defined without any reference to nondeterminism using theverifier-based definition.
Themercury logic-functional programming language establishes different determinism categories for predicate modes as explained in the reference.[8][9]
Haskell provides several mechanisms:
As seen inStandard ML,OCaml andScala
InJava, thenull reference value may represent an unsuccessful (out-of-domain) result.