[FOM] inconsistency of P

[Panu Raatikainen]

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).

Anyway:

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  
unclear.

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  
prove!


All the Best

Panu

-- 
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
Finland

E-mail: panu.raatikainen at helsinki.fi

http://www.mv.helsinki.fi/home/praatika/