Abstract
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.
Recommended Citation
G. Markowsky, "An Introduction to Algorithmic Information Theory: Its History and Some Examples," Complexity, vol. 2, no. 4, pp. 14 - 22, John Wiley & Sons, Mar 1997.
The definitive version is available at https://doi.org/10.1002/(SICI)1099-0526(199703/04)2:4<14::AID-CPLX4>3.0.CO;2-I
Department(s)
Computer Science
International Standard Serial Number (ISSN)
1076-2787
Document Type
Article - Journal
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1997 John Wiley & Sons, All rights reserved.
Publication Date
01 Mar 1997
