**Key contributors to AIT **

**Ray Solomonoff.**Provided the critical idea behind AIT and induction. See R. Solomonoff,

*Information and Control*

**7**, 1--22 (1964).

**Probably the greatest 20**

Andre Kolmogorov.

Andre Kolmogorov.

^{th}Century mathematician in the Soviet Union. Did critical work on AIT and probability. Hence the name “Kolmogorov Complexity”.

See A. N. Kolmogorov,

*Information Transmission*

**1**, 3--11 (1965). Click for Wiki biography

**Leonard Levin.**He was the first to recgonise the value self –delimiting coding in AIT.

See Leonard Levin, “Laws of information (nongrowth) and aspects of the foundation of probability theory.”

*Problems of Information Transmission*10(3): 206–210 (1974).

**Used AIT to develop the robust randomness test known by his name. See P. Martin-Lőf. The definition of random sequences.**

Per Martin-Lof.

Per Martin-Lof.

*Information and*

*Control*, 9: 602–619 (1966). Click for Wicki biography.

**Made important contributions to AIT over the years. A few minutes conversation with Peter a few years ago made me realise that I was largely ignorant of key work done in what used to be called Eastern Block countries. It seems that G á cs is the one who articulated the Martin Lőf randomness test in terms of a wager.**

Peter Gács.

Peter Gács.

G ács “Lecture Notes on Descriptional Complexity and Randomness”, which were first available a couple of decades ago, covers many key issues . Click to download

**Gregory Chaitin.**Developed AIT in the West and independently saw the need for self-delimiting coding. He recognised that the algorithmic complexity was an entropy measure. Chaitin has formulated an algorithmic version of Godel's incompleteness theorem which shows incompleteness is widespread. Chaitin also developed the idea of Omega, the somewhat mystical number that, if known, would capture all the laws of physics. See the following.

G. J. Chaitin "A theory of program size formally identical to information theory",

*Journal of the ACM*

**22 ,**547--569 (1966).

Chaitin's article in

*Scientific American*, May, 1975.

G. J. Chaitin. Information-theoretic limitations of formal systems.

*J. ACM*, 21(3) (1974).

G. J Chaitin "Gödel's Theorem and Information" International Journal of Theoretical Physics 21 (1982), pp. 941-954. Click to download

**For an update see Gregory Chaitin’s web page. Click here for web page**

**Vitányi wrote the definitive book on algorithmic information theory entitled “ An Introduction to Kolmogorov Complexity and its applications. Third Edition Springer Verlag 2008. This book is difficult to follow without some prior understanding of AIT. I would recommend you read my book first as a preparation to reading Li and Vitányi .**

Ming Li and Paul

Ming Li and Paul

See also Ming Li and Paul Vitányi "Philosophical Issues in Kolmogorov Complexity". Click here to download

See also the authors’ web
pages.

Click the following link for more about
people and applications of AIT. Click here