** Next:** PROBABILISTIC SEARCH FOR USEFUL
** Up:** BASIC CONCEPTS RELEVANT TO
** Previous:** BASIC CONCEPTS RELEVANT TO

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 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 's machine independence.
Today, even
Solomonoff himself refers to 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):
.
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 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].

** Next:** PROBABILISTIC SEARCH FOR USEFUL
** Up:** BASIC CONCEPTS RELEVANT TO
** Previous:** BASIC CONCEPTS RELEVANT TO
Juergen Schmidhuber
2003-02-12

Back to Optimal Universal Search page

Back to Program Evolution page

Back to Algorithmic Information page

Back to Speed Prior page