FOM: Re: Chaitin
Raatikainen Panu A K
Praatikainen at elo.helsinki.fi
Tue Mar 27 05:58:08 EST 2001
I would like to thank Harvey Friedman for his thoughtful comments
on our issue. There is really nothing I disagree with him.
I'll only try to comment the specific questions Harvey raised
- Panu Raatikainen
On 26 Mar 01, at 11:54, Harvey Friedman wrote:
> >a) Chaitin 1974 (mentioned by Charlie Silver).
> > For every formal system F, there is a finite constant c such
> > that F cannot prove any true statement of the form K(n) > c
> > (even thought there are infinitely many n for which this is true)
> > - here K(x) is the Kolmogorov complexity of x
>
> I think that more is true:
>
> For every consistent reasonable formal system F, there is a finite constant
> c such that F cannot prove any sentence of the form K(n) > c.
RE: I think that both your formulation and mine are slightly inexact,
namely, the proof of Chaitin's result actually requires that F proves
a sentence of the form "K(n) > m" only it is true - that is, we need
some amount of soundness and not just consistency (my wording
was even worse here) - or perhaps you meant just this by
"reasonable" ...
> Under a standard presentation of K, roughly how big does c need to be for
> ZFC? And what effect is there if we use PA (Peano Arithmetic) instead of
> ZFC?
:::
> Again, under a standard presentation of Omega (i.e., a standard setup for
> Turing machines), roughly how many digits can be determined in ZFC? And
> what effect is there if we use PA (Peano Arithmetic) instead of ZFC?
:::
> But what if we fix the presentation of Turing machines to be reasonably
> natural, in advance, and then change the theories?
>
> As a simplified example, suppose we are interested in the size of the
> smallest Turing machine TM which does not halt but cannot be proved to not
> halt in PA or ZFC. How do these sizes compare?
RE: The problem here is that in general, we cannot compute these
values (for a particular theory, with a particular coding of TMs and a
particular Gödel numbering of its syntax, it may turn out to be
possible to determine it ) - actually Chaitin's methods only provide
relatively loose upper bounds for them, contrary to what the
standard interpretation seems to suggest. Indeed, if there were any
kind of effective correspondence between F and the minimal c
(etc.) for F, one could decide the Halting Problem.
Compare: G2 provides an effective upper bound for the length of the
shortest unprovable Pi-0-1 sentence in a give theory F, i.e.
Length( Cons(F)) - but it gives absolutely no information about the
simplest such unprovable sentence. And again, if there were a
general method for finding the minimal unprovable Pi-0-1 sentence
of a theory, one could decide the undecidable.
And as I have pointed out, there are acceptable codings in which
these finite limits are the same for, say, PA and ZFC (or, for Q and
ZFC+MC, or whatever) - and we simply do not know what happens
with various "natural" or "standard" codings - as far as we know,
they may still be the same, at least for some of them. Or maybe
not.
Anyway, I guess - if it interests anybody - that for a standard
coding technique, these values would turn out to be very large.
Harvey's "simplified example" (the size of the smallest Turing
machine TM which does not halt but cannot be proved to not
halt in F) is actually not at all simple: it is it which in fact
determines the value of these limiting constants (well, in the first
case: the smallest TM which does not halt, cannot be proved to not
halt in F, and further: it cannot be proved in F what would be the
output of TM if it halted. NOTE: this is a small correction to my JPL
paper - thanks to Daniel Leivant for pointing out the gap)). But the
reply to Harvey's question is: we do not know whether there is a
difference, or whether it is the same TM.
But in any case, my arguments do show that in general, there is
no correspondence between these finite limits and the proof-
theoretical strengths of theories. And my own view is that there are
quite many rather different ways of coding Turing machines and
syntaxes all which could with equal right be called "a standard
coding", so that sticking to one and concluding something about
the resulting values of the limiting constants seems to me quite
speculative.
I think that the most natural question of this sort with a real
foundational interest still is (for some natural F):
What is the shortest true sentence (perhaps: Pi-0-1 sentence)
unprovable in F ? How large it is ?
Best
Panu Raatikainen
More information about the FOM
mailing list