- [
*Algorithmic Information Theory*.] 1987 - [
*Information, Randomness and Incompleteness: 2nd edn*.] 1990 - [
*Information-Theoretic Incompleteness*.] 1992 1998*The Limits of Mathematics*.*The Unknowable*. 1999*Exploring Randomness*. 2001*Conversations with a Mathematician*. 20022005*Meta Math!*.

- Randomness and mathematical proof. 1975. (In
*From Complexity to Life*) - An algebraic equation for the halting probability. 1988. (In
*The Universal Turing Machine*) - A random walk in arithmetic. 1992. (In
*The New Scientist Guide to Chaos*)

Here are three Gregory Chaitin lectures on his algorithmic complexity theory and the halting probability Omega. The lectures are "Randomness in arithmetic and the decline and fall of reductionism in pure mathematics", "Elegant LISP programs", "An invitation to algorithmic information theory". There is also "The limits of mathematics".

As far as I understand it [after reading this book, and then having
a long conversation with a more mathematically experienced colleague],
Chaitin's argument is as follows. Omega is the probability that a
program chosen at random halts (modulo some technicalities to make
this definition well behaved). We would like to find the value of
Omega. It is possible to increase the lower bound on Omega's value by
observing that particular programs halt. But clearly it is not
possible to decrease the upper bound except by *reasoning* that
particular programs do *not* halt, for it is not possible to
observe a program not halting. Algorithmic information theory shows
that it is not possible to reason about programs that are much larger
than one's reasoning system. So the *only* way to tighten the
upper bound on Omega is to keep increasing the size of one's reasoning
system, by adding more axioms.

There is some overlap and repetition between the chapters, but this is no bad thing, as he gets to explain the same ideas from different angles. These are edited transcripts of lectures, and have a rather chatty, even exuberant, style, but lack some of the polish that might be expected from a written essay. Never mind -- this is a clear explanation of some deep results, from the original inventor himself. Mind expanding stuff.

Chaitin produced his first theoretical results in the 1970s.

You can't prove
that an *N*-bit string is algorithmically incompressible if *N
*is larger than the complexity of your axioms. You can't prove that
an *N*-bit string is algorithmically irreducible if it has more
bits than the axioms you're using for the proof.

What he has done since is program up these theorems, in a form of Lisp. This has allowed him to determine the actual (surprisingly small) values of numerical constants in some of his undecidability theorems, and lower bounds on the halting probability. Probably only a mathematician would make the following definition:

Call a program "elegant"
if no smaller program has the same output.

(Although, to be fair, he does say that these "elegant" programs are not the kind of things you would want to write for real!) He goes on to explain the conclusions of his work.

The existence
of irreducible mathematical facts shows that in some cases there is
absolutely no compression, no structure or pattern at all in
mathematical truth.

However, this is not necessarily a problem.

I don't believe
that all this work on the foundations of mathematics has changed at
all the way mathematicians actually work. Gödel's incompleteness
theorem was initially very shocking. But then mathematicians noticed
that the kind of assertion that Gödel constructed that's true but
unprovable is not the kind of assertion that you deal with in your
everyday work as a mathematician. And I think it's fair to say that
about Omega too.

But what has made a difference to the working mathematician is the computer. A whole new subject is opening up: empirical, or experimental, mathematics.

This is a more accessible version of Chaitin's work than his earlier, more academic, book. He explains the background leading up to the definition and properties of a rather fascinating number: Omega, the uncomputable Halting probability. On the way, he leads us through discussions about the value of multiple proofs of deep theorems (they highlight different aspects of the theorems), the unspeakability of the majority of real numbers, and the role of randomness in mathematics.

This is a nice little book, spoiled for me by only one thing! A small
thing, admittedly! But annoying nonetheless! I refer to the profusion of
exclamation marks!!! At the time of reading, it felt like nearly every
sentence ended with one. On looking back, I see that they are not *quite*
that frequent, but still frequent enough to be irritating. The editor
should have removed all of them -- the material is exciting enough in its
own right without the need to keep telling us so.