Inductive inference

Around 1960, Ray Solomonoff founded the theory of universal inductive inference, the theory of prediction based on observations. Given is the beginning of some sequence of symbols. Which symbol will be next? Solomonoff's theory provides an answer that is optimal in a certain sense. Unlike Karl Popper's informal theory of inductive inference, Solomonoff's is mathematically sound.

Fundamental ingredients of the theory are the concepts of algorithmic probability and Kolmogorov complexity. The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p. Given some p and any computable but unknown probability distribution from which x is sampled, the universal prior and Bayes' formula can be used to predict the yet unseen parts of x in optimal fashion.