- 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. Around1960 ,Ray Solomonoff invented the concept of algorithmic probability: take auniversal computer and randomly generate an input program. The program will compute some possiblyinfinite 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 ofinductive 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 . TheKolmogorov complexity of any computable object is the length of the shortest program that computes it and then halts. Theinvariance 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.
