An Introduction to Algorithmic Information Theory: Its History and Some Examples

The goal of this paper is to provide a simple introduction to Algorithmic Information Theory (AIT) that will highlight some of the main ideas without presenting too many details. More technical treatments of these ideas can be found in References [1], [2], [3] and [4], which are listed at the end of the paper. The main ideas of Algorithmic Information Theory will be presented using English as the underlying programming language. The presentation illustrates the fact that the same arguments can be expressed in any other reasonable language and that the main results have a robust universality across all reasonable languages. This paper grew out of a short course on AIT that Gregory Chaitin presented in June 1994, at the University of Maine. I helped with the course and observed some of the topics that proved most difficult for students. I presented a series of lectures based on these observations at the 1995 Summer School on Algorithmic Information Theory held in Mangalia Romania. The text of those lectures, and others from that workshop, can be found in The Journal of Universal Computer Science.[8] All the material presented here is based on the work of Gregory Chaitin