Algorithmic Information Theory (Solomonoff / Kolmogorov)

Editorial record

Plain-language summary

In the 1960s Ray Solomonoff, Andrey Kolmogorov, and Gregory Chaitin independently proposed measuring how complex a string of data is by the size of the smallest computer program that can generate it. A string that needs a long program is effectively random, while a compressible one is simple. Solomonoff used this idea to build a theory of prediction that favors the simplest explanation consistent with the data. These concepts connect compression, probability, and learning, and they inform how researchers reason about generalization and Occam's razor in machine learning.