Invitation to algorithmic information theory

Abstract

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.