arXiv:chao-dyn/9407003v1 7 Jul 1994
THE LIMITS OF MATHEMATICS
G. J. Chaitin IBM, P O Box 704 Yorktown Heights, NY 10598
[email protected]
Draft July 7, 1994
To Fran¸coise
Preface In a remarkable development, I have constructed a new definition for a self-delimiting universal Turing machine (UTM) that is easy to program and runs very quickly. This provides a new foundation for algorithmic information theory (AIT), which is the theory of the size in bits of programs for self-delimiting UTM’s. Previously, AIT had an abstract mathematical quality. Now it is possible to write down executable programs that embody the constructions in the proofs of theorems. So AIT goes from dealing with remote idealized mythical objects to being a theory about practical down-to-earth gadgets that one can actually play with and use. This new self-delimiting UTM is implemented via an extremely fast LISP interpreter written in C. The universal Turing machine U is written in this LISP. This LISP also serves as a very high-level assembler to put together binary programs for U. The programs that go into U, and whose size we measure, are bit strings. The output from U, on the other hand, consists of a single LISP S-expression, in the case of finite computations, and of an infinite set of these S-expressions, in the case of infinite computations. The LISP used here is based on the version of LISP that I used in my book Algorithmic Information Theory, Cambridge University Press, 1987. The difference is that a) I have found a self-delimiting way to give binary data to LISP programs, and b) I have found a natural way to handle unending computations, which is what formal axiomatic systems are, in LISP. Using this new software, as well as the latest theoretical ideas, it is now possible to give a self-contained “hands on” course presenting very concretely my latest proofs of my two fundamental informationv
vi theoretic incompleteness theorems. The first of these theorems states that an N-bit formal axiomatic system cannot enable one to exhibit any specific object with program-size complexity greater than N + c. The second of these theorems states that an N-bit formal axiomatic system cannot enable one to determine more than N + c′ scattered bits of the halting probability Ω. Most people believe that anything that is true is true for a reason. These theorems show that some things are true for no reason at all, i.e., accidentally, or at random. The latest and I believe the deepest proofs of these two theorems were originally presented in m