CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

Chaitin: The Limits of Mathematics

pubs/books/online/math/chaitin/
This book features a definitive reformulation of algorithmic information theory with new more constructive definitions of program-size complexity. It is a revised version of the course notes given to the participant at the limits of mathematics short course, University of Maine, Orono, Maine, June 1994. The book discusses a new definition for a self-delimiting universal Turing machine (UTM) that is easy to program and runs very quickly. It then uses this to provide a new foundation for algorithmic information theory (AIT), which is the theory of the size in bits of programs for self-delimiting UTM's. This new self-delimiting UTM is implemented via an extremely fast LISP interpreter written in C. Source code for the LISP interpreter is included in the book. This directory includes a copy of a 4 page summary of the book and the 270-page book itself, in LaTeX, dvi, and PostScript formats. Three different versions of the book (and source) are included, in the three directories lm_1, lm_2, and lm_3. The difference between the three is as follows: An N-bit formal axiomatic system cannot enable one to exhibit any specific object with program-size complexity greater than N+c. An N-bit formal axiomatic system cannot enable one to determine more than N+c' scattered bits of the halting probability Omega. LM I: c = 2359 bits and c' = 7581 bits. LM II: c = 1127 bits and c' = 3689 bits. LM III: c = 994 bits and c' = 3192 bits. LM IV: c = 735 bits and c' = 2933 bits. 
Origin:   

   Email to chao-dyn@xyz.lanl.gov with Subject line
      get 9407003
Version: Draft of 7-JUL-94 Requires: LaTeX or PostScript Updated: 14-JUL-94 CD-ROM: Prime Time Freeware for AI, Issue 1-1 Author(s): Gregory J. Chaitin IBM, P O Box 704 Yorktown Heights, NY 10598 Keywords: Authors!Chaitin, Books!Limits of Mathematics, Interpreters!Lisp, Lisp!Implementations Contains: lm_?/lisp_src.tgz source code from the book lm_?/limits.tgz 250 page book, with LaTeX, dvi, ps summary.tgz 4 page summary, with LaTeX, dvi, ps References: Gregory J. Chaitin, "Algorithmic Information Theory", Cambridge University Press, 1987. Gregory J. Chaitin, "Information-theoretic incompleteness", Applied Mathematics and Computation 52:83-101, 1992. Gregory J. Chaitin, "Information-Theoretic Incompleteness", World Scientific, 1992.
Last Web update on Mon Feb 13 10:38:30 1995
AI.Repository@cs.cmu.edu