Algorithmic probability


Algorithmic probability

Algorithmic probability is a concept in theoretical computer science; it quantifies the idea of theories and predictions with reference to short programs and their output. Around 1960, Ray Solomonoff invented the concept of algorithmic probability: take a universal computer and randomly generate an input program. The program will compute some possibly infinite output.

The algorithmic probability of any given finite output prefix "q" is the sum of the probabilities of the programs that compute something starting with "q". Certain long objects with short programs have high probability.

Algorithmic probability is the main ingredient of Ray Solomonoff's theory of inductive inference, the theory of prediction based on observations. Given a sequence of symbols, which will come next? Solomonoff's theory provides an answer that is optimal in a certain sense, although it is incomputable. Unlike, for example, Karl Popper's informal inductive inference theory, however, Solomonoff's is mathematically rigorous.

Algorithmic probability is closely related to the concept of Kolmogorov complexity. The Kolmogorov complexity of any computable object is the length of the shortest program that computes it and then halts. The invariance theorem shows that it is not really important which computer we use.

Solomonoff's enumerable measure is universal in a certain powerful sense, but it ignores computation time.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Algorithmic information theory — is a subfield of information theory and computer science that concerns itself with the relationship between computation and information. According to Gregory Chaitin, it is the result of putting Shannon s information theory and Turing s… …   Wikipedia

  • Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… …   Wikipedia

  • Prior probability — Bayesian statistics Theory Bayesian probability Probability interpretations Bayes theorem Bayes rule · Bayes factor Bayesian inference Bayesian network Prior · Posterior · Likelihood …   Wikipedia

  • Ray Solomonoff — (born 1926, Cleveland, Ohio, son of Russianimmigrants) invented [http://scholarpedia.org/article/Algorithmic probability Algorithmic Probability] in 1960. He first described his results at a Conference at Cal Tech, 1960, [Paper from conference on …   Wikipedia

  • Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… …   Wikipedia

  • Randomness — Random redirects here. For other uses, see Random (disambiguation). For a random Wikipedia article, see Special:Random. For information about Wikipedia s random article feature, see Wikipedia:Random. Randomness has somewhat differing meanings as… …   Wikipedia

  • Occam's razor — For the aerial theatre company, see Ockham s Razor Theatre Company. It is possible to describe the other planets in the solar system as revolving around the Earth, but that explanation is unnecessarily complex compared to the modern consensus… …   Wikipedia

  • Marcus Hutter — (born 1967) is a German computer scientist and professor at the Australian National University. Hutter was born and educated in Munich, where he studied physics and computer science. In 2000 he joined Jürgen Schmidhuber s group at the Swiss… …   Wikipedia

  • Inductive inference — This article is about the mathematical concept, for inductive inference in logic, see Inductive reasoning. Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations; for… …   Wikipedia

  • COMPUTER SCIENCE — The term Computer Science encompasses three different types of research areas: computability, efficiency, and methodology. General Introduction Computability deals with the question of what is mechanically computable. The most natural way to… …   Encyclopedia of Judaism