This new self-delimiting UTM is implemented via software written in a new version of LISP that I invented especially for this purpose. This LISP was designed by writing an interpreter for it in Mathematica that was then translated into C. I have tested this software by running it on IBM RS/6000 workstations with the AIX version of UNIX.

Using this new software and the latest theoretical ideas, it is now
possible to give a self-contained ``hands on'' mini-course presenting
very concretely my latest proofs of my two fundamental
information-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.

As is shown in this course, the algorithms considered in the proofs of
these two theorems are now easy to program and run, and by looking at
the size in bits of these programs one can actually, for the first
time, determine exact values for the constants *c* and *c'*.

I used this approach and software in an intensive short course on the
limits of mathematics that I gave at the University of Maine in Orono
in the summer of 1994. I also lectured on this material during a stay
at the Santa Fe Institute in the
spring of 1995, and at a
meeting
at the Black Sea University in Romania in the summer of 1995. A
summary of the approach that I used on these three occasions will
appear under the title ``A new version of algorithmic information
theory'' in a forthcoming issue of the new magazine
*Complexity*,
which has just been launched by the Santa Fe Institute and Wiley. A
less technical discussion of the basic ideas that are involved ``How
to run algorithmic information theory on a computer'' will also appear
in *Complexity.*

After presenting this material at these three different places, it became obvious to me that it is extremely difficult to understand it in its original form. So next time, at the Rovaniemi Institute of Technology in the spring of 1996, I am going to use the new, more understandable software in this report; everything has been redone in an attempt to make it as easy to understand as possible.

For their stimulating invitations, I thank Prof. George Markowsky of the University of Maine, Prof. Cristian Calude of the University of Auckland, Prof. John Casti of the Santa Fe Institute, and Prof. Veikko Keränen of the Rovaniemi Institute of Technology. And I am grateful to IBM for supporting my research for almost thirty years, and to my current management chain at the IBM Research Division, Dan Prener, Christos Georgiou, Eric Kronstadt, Jeff Jaffe, and Paul Horn.

This report includes the Mathematica code for the LISP interpreter lisp.m, and the LISP runs *.r used to present the information-theoretic incompleteness theorems of algorithmic information theory. This report also includes the input to the interpreter *.l for producing these LISP runs, and the C version of the interpreter lisp.c.

So far this is fairly standard. The new idea is this. We define our
standard self-delimiting universal Turing machine as follows. Its
program is in binary, and appears on a tape in the following form.
First comes a LISP expression, written in ASCII with 8 bits per
character, and terminated by an end-of-line character `\n'. The TM
reads in this LISP expression, and then evaluates it. As it does
this, two new primitive functions `read-bit` and
`read-exp` with no arguments may be used to read more from the
TM tape. Both of these functions explode if the tape is exhausted,
killing the computation. `read-bit` reads a single bit from
the tape. `read-exp` reads in an entire LISP expression, in
8-bit character chunks, until it reaches an end-of-line character
`\n'.

This is the only way that information on the TM tape may be accessed, which forces it to be used in a self-delimiting fashion. This is because no algorithm can search for the end of the tape and then use the length of the tape as data in the computation. If an algorithm attempts to read a bit that is not on the tape, the algorithm aborts.

How is information placed on the TM tape in the first place? Well, in
the starting environment, the tape is empty and any attempt to read it
will give an error message. To place information on the tape, one
must use the primitive function `try` which tries to see if an
expression can be evaluated.

Consider the three arguments α, β and γ of
`try`. The meaning of the first argument is as follows. If
α is `no-time-limit`, then there is no depth limit.
Otherwise α must be an unsigned decimal integer, and gives the
depth limit (limit on the nesting depth of function calls and
re-evaluations). The second argument β of `try` is the
expression to be evaluated as long as the depth limit α is not
exceeded. And the third argument γ of `try` is a list
of bits to be used as the TM tape.

The value ν returned by the primitive function `try` is
a triple. The first element of ν is `success` if the
evaluation of β was completed successfully, and the first
element of ν is `failure` if this was not the case. The
second element of ν is `out-of-data` if the evaluation
of β aborted because an attempt was made to read a non-existent
bit from the TM tape. The second element of ν is
`out-of-time` if evaluation of β aborted because the
depth limit α was exceeded. These are the only possible error
flags, because this LISP is designed with maximally permissive
semantics. If the computation β terminated normally instead of
aborting, the second element of ν will be the result produced
by the computation β, i.e., its value. That's the second
element of the list ν produced by the `try` primitive
function.

The third element of the value ν is a list of all the arguments
to the primitive function `display` that were encountered
during the evaluation of β. More precisely, if
`display` was called *N* times during the evaluation of
β, then the third element of
ν will be a list of *N* elements. The
*N* arguments of `display` appear in
the third element of ν in
chronological order. Thus `try` can not only be used to
determine if a computation β reads too much tape or goes on too
long (i.e., to greater depth than α), but `try` can also
be used to capture all the output that β displayed as it went
along, whether the computation β aborted or not.

In summary, all that one has to do to simulate a self-delimiting
universal Turing machine *U(p)* running on the binary program
*p* is to write

try no-time-limit 'eval read-exp pThis is an M-expression with parentheses omitted from primitive functions. (Recall that all primitive functions have a fixed number of arguments.) With the parentheses supplied, it becomes the S-expression

(try no-time-limit ('(eval(read-exp))) p)This says that one is to read a complete LISP S-expression from the TM tape

Some more primitive functions have also been added. The 2-argument
function `append` denotes list concatenation, and the
1-argument function `bits` converts an S-expression into the
list of the bits in its ASCII character string representation. These
are used for constructing the bit strings that are then put on the TM
tape using `try`'s third argument γ. We also provide
the 1-argument functions `size` and `length` that
respectively give the number of characters in an S-expression, and the
number of elements in a list. Note that the functions
`append`, `size` and `length` could be programmed
rather than included as built-in primitive functions, but it is
extremely convenient and much much faster to provide them built in.

Finally a new 1-argument identity function `debug` with the
side-effect of outputting its argument is provided for debugging.
Output produced by `debug` is invisible to the ``official''
`display` and `try` output mechanism. `debug`
is needed because `try` α β γ suppresses
all output θ produced within its depth-controlled evaluation of
β. Instead `try` collects all output θ from
within β for inclusion in the final value ν that
`try` returns, namely ν = (success/failure, value of
β, θ).

Then the theory of LISP program-size complexity is developed a little
bit. LISP program-size complexity is extremely simple and concrete.
In particular, it is easy to show that it is impossible to prove that
a self-contained LISP expression is elegant, i.e., that no smaller
expression has the same value. More precisely, a formal axiomatic system of
LISP complexity *N* cannot prove that a
LISP expression is elegant if the LISP expression is more than
*N* + 410 characters long.
See godel.r.

Next we define our standard self-delimiting universal Turing machine
*U(p)* using

cadr try no-time-limit 'eval read-exp pas explained in the previous section.

Next we show that

with *c* = 432. Here *H*(...) denotes the size in bits of
the smallest program that makes our standard universal Turing machine
compute *...*. Thus this inequality states that the information
needed to compute the pair (*x*, *y*) is bounded by a constant
*c* plus the sum of the information needed to compute *x*
and the information needed to compute *y*. Consider

cons eval read-exp cons eval read-exp nilThis is an M-expression with parentheses omitted from primitive functions. With all the parentheses supplied, it becomes the S-expression

(cons (eval (read-exp)) (cons (eval (read-exp)) nil))

Consider a binary string *x* whose size is | *x* | bits. In
utm.r we also show that

and

with *c* = 1106 and *c'* = 1024. As before, the programs
for doing this are exhibited and run.

Next we turn to the self-delimiting program-size complexity
*H*(*X*) for infinite r.e. sets *X*. This is defined to be
the size in bits of the smallest LISP expression *x* that
executes forever without halting and outputs the members of the r.e.
set *X* using the LISP primitive `display`, which is an
identity function with the side-effect of outputting the value of its
argument. Note that this LISP expression *x* is allowed to read
additional bits or expressions from the TM tape using the primitive
functions `read-bit` and `read-exp` if *x* so
desires. But of course *x* is charged for this; this adds to
*x*'s program size.

It is in order to deal with such unending expressions *x* that
the LISP primitive function for time-limited evaluation `try`
captures all output from `display` within its second argument
β.

Now consider a formal axiomatic system *A* of complexity
*N*, i.e., with a set of theorems *T _{A}* that
considered as an r.e. set as above has self-delimiting program-size
complexity

Next we show two different ways to calculate the halting probability
Ω of our standard self-delimiting universal Turing machine
in the limit from below. See omega.r
and omega2.r. The first way of doing
this, omega.r, is straight-forward. The second way to
calculate Ω, omega2.r, uses a more clever method.
Using the clever method as a subroutine, we show that if
Ω* _{N}* is the first

with *c* = 8000. Again this is done with a program that can
actually be run and whose size gives us a value for *c*. See
omega3.r.

Consider again the formal axiomatic system *A* with complexity
*N*, i.e., with self-delimiting program-size complexity
*H*(*T _{A}*) =

Last but not least, the philosophical implications of all this should be discussed, especially the extent to which it tends to justify experimental mathematics. This would be along the lines of the discussion in my talk transcript ``Randomness in arithmetic and the decline and fall of reductionism in pure mathematics''.

This concludes our ``hands-on'' mini-course on the information-theoretic limits of mathematics.

Here is another complete set of source (and output). This time the code is heavily commented, debug output is included, auxiliary functions are tested, and the C version of the LISP interpreter was also used. Source code: xexamples.l, xgodel.l, xutm.l, xgodel2.l, xomega.l, xomega2.l, xomega3.l, xgodel3.l. LISP runs: xexamples.r, xgodel.r, xutm.r, xgodel2.r, xomega.r, xomega2.r, xomega3.r, xgodel3.r.

- G. J. Chaitin,
``Randomness in arithmetic and the decline
and fall of reductionism in pure mathematics'',
in J. Cornwell,
*Nature's Imagination,*Oxford University Press, 1995, pp. 27-44. - G. J. Chaitin,
``The Berry paradox'',
*Complexity*1:1 (1995), pp. 26-30. - G. J. Chaitin,
``A new version of algorithmic information theory'',
*Complexity,*to appear. - G. J. Chaitin,
``How to run algorithmic information theory on a computer'',
*Complexity,*to appear.