Key contributors to AIT

Ray Solomonoff.   Provided the critical idea behind AIT and induction. See   R. Solomonoff, Information and Control7 , 1--22 (1964).

Andre Kolmogorov.
  Probably the greatest 20th 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).

Per Martin-Lof.
  Used AIT to develop the robust randomness test known by his name. See P. Martin-Lőf. The definition of random sequences. Information and Control , 9: 602–619 (1966). Click for Wicki biography.

Peter Gács.
  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.   

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

Ming Li and Paul
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 .

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