An Invitation to Algorithmic Information Theory

Gregory Chaitin
IBM Research
P.O. Box 704
Yorktown Heights, NY 10598


I'll outline the version of my ``Limits of Mathematics'' course that I gave at the Rovaniemi Institute of Technology in May 1996. The purpose of this course is to illustrate the proofs of the key information-theoretic incompleteness theorems of algorithmic information theory by means of algorithms written in a specially designed version of LISP. At Rovaniemi I used a LISP interpreter written in Mathematica, and it is merely 300 lines of Mathematica code.

The feedback from the participants was very encouraging. They said that it was possible in a very concrete manner to take hold of the abstract concepts involved.

Course materials including handouts and LISP and Mathematica code are available by e-mail from the author.

  • Homepage of Gregory Chaitin