Is not deterministically the same as random

A deterministic algorithm is an algorithm in which only defined and reproducible states occur. The same output always follows for the same input and additionally the same sequence of states is run through. The subsequent processing step of the algorithm is clearly defined at each point in time.[1] This also means that all intermediate results within the algorithm are always the same.[1]

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 in each discrete processing step is meant.

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.[2] However, the reverse is not true: there are algorithms that are non-deterministic, but nonetheless determined (i.e. deliver the same result).[2] For example, the QuickSort sorting algorithm always divides a given list into partial lists, the size of which can be selected at random, but the result is always the same. Quicksort is thus nondeterministic since its intermediate results can differ, but it is determined since the end result is always identical.[1]

Conversely, non-reproducible and undefined states can occur with a nondeterministic, randomized algorithm. For example, an algorithm that returns 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 their own complexity class in complexity theory.

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)

The deals with determinism as a property of the world as a whole philosophical determinism[3]. The question of whether the physical processes in the world are deterministic has far-reaching consequences for the understanding of free will, among other things[4] and the concept of God[3].

Individual evidence

1. abcDeterminism of an Algorithm. (PDF) In: Computer science Duden. Bibliographisches Institut, Berlin, 2001, accessed on January 31, 2018.
2. abBettina Selig, Vera Kern and Tilman Walther: Properties of algorithms. Tilman Walther, March 2004, accessed January 31, 2018.
3. abPeter 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 a free will? In: Philosophy understandable. Bielefeld University - Philosophy Department, October 3, 2005, accessed on January 31, 2018.

literature

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to automata theory, formal languages ​​and complexity theory. 2nd, revised edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5.

Categories:algorithm

Status of information: 11/22/2020 3:53:07 AM CET

Source: Wikipedia (authors [version history]) License: CC-BY-SA-3.0

Changes: All images and most of the design elements associated with them have been removed. Some of the icons have been replaced by FontAwesome icons. Some templates have been removed (such as "Article worth reading", "Excellent article") or rewritten. Most of the CSS classes have been removed or standardized.