FOM: On Chaitin's theorems

[Joe Shipman]

In defense of Chaitin, I have always found his approach by far the
easiest way of establishing incompleteness theorems, and his
philosophical insight that the strength of theories is ultimately
dependent on their algorithmic information content is important.
Chaitin's result that the halting probability of a computation-universal
system is maximally compressed information is also useful in various
contexts.

On the other hand, Chaitin's more recent remarks about the "randomness"
of mathematical truth seem muddled to me.  Yes, there are parameterized
exponential Diophantine equations (and probably regular diophantine
equations too), the existence of solutions to which is an absolutely
random function of the parameter in various senses, but it is not
surprising that there are mathematical statements which are true for no
particular reason.  This would only become interesting if the statements
themselves were small enough to be interesting.

The relevance of algorithmic information to the incompleteness theorems
and to mathematics generally is obscured because the well-explored
hierarchy of logical strengths of theories does not seem to correspond
to amount of algorithmic information in the theory.  Some very strong
theories seem to have much simpler axiomatizations than much weaker
ones.  We need a better way to measure (an upper bound on) the
algorithmic complexity of a theory.

The most straightforward way to do this is to start with the predicate
calculus as a computational base, and define the complexity of a theory
to be the length of the shortest axiomatization, converting
non-finitely-axiomatizable theories into finitely axiomatizable
conservative extensions ones by introducing new predicates to Skolemize
axiom schemes.  (Consider GB versus ZF.)  But there may well be ways to
represent the size of a theory involving other computational bases that
are superior for relating "size" of a theory to logical strength.

PA and ZFC both seem to have the property that they are "simpler" (in
some inexact sense) than any logically stronger consistent theories.
I'd like to see someone either dispute this assertion or suggest other
examples of the phenomenon.

-- Joe Shipman