FOM: Re: Chaitin

[Raatikainen Panu A K]

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