Determinism (algorithm)

from Wikipedia, the free encyclopedia

A deterministic algorithm is an algorithm in which only defined and reproducible states occur. For the same input always follows the same issue and also the same sequence is executed on states. The subsequent processing step of the algorithm is clearly defined at each point in time. This also means that all intermediate results within the algorithm are always the same.

Colloquially, one could say: "An instruction in the algorithm always follows the same instruction under the same conditions." With this formulation, however, it should be noted that under "same conditions" exactly the same intermediate results and data are meant in every discrete processing step.

The term determinism is to be distinguished from the term determinism : A deterministic algorithm is always determined, i. In other words, it always delivers the same output with the same input. However, the reverse is not true: there are algorithms that are non-deterministic, but nonetheless determined (i.e. deliver the same result). For example, the quicksort sorting algorithm always divides a given list into sub-lists, which can be randomly selected in terms of size, but the result is always the same. Quicksort is therefore nondeterministic, since its intermediate results can differ, but it is determined, since the end result is always identical.

Conversely, with a nondeterministic, randomized algorithm, non-reproducible and undefined states can occur. For example, an algorithm that delivers a (theoretical) random number has nondeterministic behavior.

Nondeterministic Turing machines play a major role in theoretical computer science : They enable an algorithm to quasi “guess”. This means that many problems can be solved with much less effort. Such Turing machines define the complexity theory own complexity class .

Further properties of an algorithm are

  • Finiteness (static: finite description, dynamic: finite number of resources during execution)
  • Complexity (required computing time and storage space, high or low)
  • Termination (result after a finite number of steps. Expression: terminating / not terminating)
  • Determination (with the same input, the same result, characteristics: determined, not determined)

Determinism as a property of the world as a whole is treated 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 understanding of God , among other things .

See also

Individual evidence

  1. ↑ a b c Determinism of an algorithm. (PDF) In: Informatik Duden. Bibliographisches Institut, Berlin, 2001, accessed on January 31, 2018 .
  2. ↑ a b Bettina Selig, Vera Kern and Tilman Walther: Properties of Algorithms. Tilman Walther, March 2004, accessed January 31, 2018 .
  3. ^ A b Peter Schulte, Ansgar Beckermann: Determinism. In: Philosophy understandable. Bielefeld University - Philosophy Department, March 5, 2005, accessed on January 31, 2018 .
  4. ↑ Ansgar Beckermann: Do we have free will? In: Philosophy understandable. Bielefeld University - Philosophy Department, October 3, 2005, accessed on January 31, 2018 .

literature