[FOM] inconsistency of P
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”
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
Ph.D., University Lecturer
Docent in 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