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
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 recognise 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
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
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