History spotlights / Selected references

In 1965, A. N. Kolmogorov (1903-1987), founder of modern axiomatic probability theory [Kolmogorov, 1933], was the first to introduce a variant of the complexity measure $K$ for its own sake [Kolmogorov, 1965]. Levin (1984) cites announcements of Kolmogorov's lectures on this subject dating back to 1961. In an independent and even earlier work, R. J. Solomonoff (1964) had already come up with the same measure as a by-product of his work on algorithmic probability and inductive inference (a preliminary version of his paper is dated 1960). Both Solomonoff and Kolmogorov observed $K$'s machine independence. Today, even Solomonoff himself refers to $K$ as ``Kolmogorov complexity,'' e.g., [Solomonoff, 1986]. In 1969, G. J. Chaitin independently also published the essential concepts [Chaitin, 1969] (some hints were already provided at the end of his 1966 paper). Important related early work is described in [Martin-Löf, 1966,Gács, 1974,Schnorr, 1971]. Apparently, L. A. Levin was the first to introduce and analyze today's ``standard form'' of Kolmogorov complexity based on halting programs and prefix codes [Levin, 1974], see also [Gács, 1974,Levin, 1973a,Levin, 1976,Zvonkin and Levin, 1970]. Levin proved equation (3): $K(s) = H(s) + O(1)$. The importance of prefix codes was independently mentioned by Chaitin (1975), who also proved (3) and attributes part of the argument to N. Pippenger. Levin introduced $Kt$ complexity and the universal optimal search algorithm (see, e.g., [Levin, 1973b] and [Levin, 1984], where related ideas are attributed to Adleman - see also [Adleman, 1979]). Other generalizations of Kolmogorov complexity have been proposed, e.g., [Hartmanis, 1983], but for more details see the contributions in [Watanabe, 1992]. Easily computable approximations of the MDL principle were formulated by Wallace and Boulton (1968) and Rissanen (1978, 1983, 1986). Such approximations build the basis of most -- if not all -- current machine learning applications, e.g., [Quinlan and Rivest, 1989,Gao and Li, 1989,Milosavljevic and Jurka, 1993,Pednault, 1989]. Barzdin, referred to in [Zvonkin and Levin, 1970] (see also Barzdin, 1988), related Kolmogorov complexity to a variant of Gödel's incompleteness theorem, a subject which became a central theme of Chaitin's research [Chaitin, 1987]. Meanwhile, the theory of Kolmogorov complexity has split into many subfields. An excellent overview and many additional details on the history are given in Li and Vitanyi's book (1993) and also in [Cover et al., 1989]. See [Schmidhuber, 1995] for an application to fine arts. This section was partly inspired by presentations found in [Chaitin, 1987], [Li and Vitányi, 1993], and [Solomonoff, 1986].

Back to Optimal Universal Search page
Back to Program Evolution page
Back to Algorithmic Information page
Back to Speed Prior page