Deterministic algorithm
A deterministic algorithm is an algorithm in which only defined and reproducible states occur. The same input is always followed by the same output and, in addition, the same sequence of states is run through. At each point in time, the subsequent processing step of the algorithm is uniquely defined. This also means that all intermediate results within the algorithm are always the same.
Colloquially, one might say, "An instruction in the algorithm is always followed by the same instruction under the same conditions." With this formulation, however, it should be noted that under "the same conditions" exactly the same intermediate results and data are meant in each discrete processing step.
The term determinism must be distinguished from the term determinacy: A deterministic algorithm is always determinate, i.e., it always produces the same output given the same input. The converse, however, does not hold: for example, there are algorithms that are nondeterministic but still deterministic (i.e., produce the same result). For example, the sorting algorithm Quicksort always divides a given list into sublists, which can be randomized in size, but the result is always the same. Thus, Quicksort is non-deterministic, since its intermediate results may differ, but deterministic, since the final result is always identical.
Conversely, a non-deterministic randomized algorithm may have non-reproducible and undefined states. For example, an algorithm that returns a (theoretical) random number has a non-deterministic behavior.
Non-deterministic Turing machines play a major role in theoretical computer science: They allow an algorithm to "guess", so to speak. This makes many problems solvable with much less effort. Such Turing machines define their own complexity class in complexity theory.
Other properties of an algorithm are
- Finiteness (static: finite description, dynamic: finite resources during execution)
- Complexity (amount of computing time and memory required, high or low)
- Terminatedness (result after finite number of steps. Characteristic: terminating/non-terminating)
- Determinacy (same result for the same input, type: determined, not determined)
Determinism as a property of the world as a whole is dealt with by philosophical determinism. The question of whether the physical processes in the world are deterministic has far-reaching consequences for the understanding of free will and the concept of God, among other things.
See also
- Randomized algorithm (Stochastic algorithm)
- Causality
