[FOM] inconsistency of P

Panu Raatikainen panu.raatikainen at helsinki.fi
Sun Oct 2 02:33:03 EDT 2011

Lainaus "Monroe Eskew" <meskew at math.uci.edu>:

> Tao's claim is that the Chaitin machine must include a proof checker
> for T, which is right.  He then stipulated a definition of complexity
> of a theory T as the length of the smallest machine that checks proofs
> in T.  Modulo some basic choices on coding Turing machines, which
> seems to be necessary for Kolmogorov complexity to make sense, Tao's
> notion seems well-defined.  Furthermore, we can assume these choices
> are held constant in the context of Nelson's argument, in which I see
> no mention of variations on coding.

What you say is more or less right (though, a coding of Turing  
machines is not sufficient, as you seem to suggest; also an  
arithmetization of the language of PA (or whatever) is needed; and  
these are two separate issues; that was my initial point).


Chaitin’s theorem can be proved in many ways, and not all of them  
involve “a Chaitin machine”. (I give one alternative in my paper.)

A proof with a Chaitin machine provides, for a theory T, a  
sufficiently large l such that T cannot prove K(n) > l for any n.  
However, the constant l provided by this kind of proof may not be -  
and usually is not - the *minimal* such number. Sometimes, it is a far  
cry from the minimal! Ignoring this has caused a lot of confusion.

In the literature, we have called the *minimal* number c for T such  
that T cannot prove K(n) > c (for any n) “the characteristic constant”  
of T.

Now as Tao correctly notes later (let us fix an arithmetization), a  
relatively simple theory T may have a subtheory S which has an  
astronomically large Kolmogorov complexity.

But of course, being a subtheory, it cannot prove more cases of K(n) >  
m than T. So the minimal “characteristic” constant of S cannot be  
larger than that of T.

So Tao’s original claim, that “Basically, in order for Chaitin’s  
theorem (10) to hold, the Kolmogorov complexity of the consistent  
theory T has to be less than l ” is false, or at least ambiguous and  

In sum, there is no connection between the Kolmogorov complexity of a  
theory and the number (always finite) of cases of K(n) > m that it can  

All the Best


Panu Raatikainen

Ph.D., University Lecturer
Docent in Theoretical Philosophy

Theoretical Philosophy
Department of Philosophy, History, Culture and Art Studies
P.O. Box 24  (Unioninkatu 38 A)
FIN-00014 University of Helsinki

E-mail: panu.raatikainen at helsinki.fi


More information about the FOM mailing list