FOM: Re: Chaitin

[Raatikainen Panu A K]

On 27 Mar 01, at 20:28, Harvey Friedman wrote:
 
> THEOREM. Let T be a consistent recursively axiomatizable extension of EFA
> (exponential function arithmetic), possibly with additional sorts. There is
> a constant c such that for all n, K(n) > c is not provable in T.

RE: OK, I surrender;  I can only say that the standard proofs of 
Chaitin's theorem have made some soundness assumptions. (I 
don't know if I really followed Harvey's ingenious proof - I'll have to 
reflect it for some time. But I have no reason to doubt it.)
- one question: does this proof provide an effective upper bound for 
c ? 

Friedman wrote:

> SOME REVERSE MATH OF KOLMOGOROV COMPLEXITY
> 
> Sigma-0-1 induction is sufficient to prove for all n, K(n) exists, and to
> prove the existence of Kolmogorov random integers.
> 
> What is the status over EFA of
> i) for all n, K(n) exists;
> ii) the function K is defined on every interval [0,n];
> iii) the function K achieves a maximum value on every interval [0,n];
> iv) there is a Kolmogorov random bit sequence of each length.

(etc.)

RE: This sounds very exciting - I just want to remark that it is 
interesting that although it is possible to formalize the basic 
recursion theory in HA (see e.g. Troelstra and van Dalen, Vol. 1, p. 
152-), it is *not* possible to prove i) "for all n, K(n) exists" in HA, for 
it requires the Least Number Principle (and thus classical logic) 
applied to  a Sigma-O-1 formula. 


Friedman wrote:

> I am raising the possibility of at least some comparison between PA and ZFC
> on this basis.

RE. OK. But what I feel is that it is still much more interesting to 
compare PA and ZFC with respect to some natural 
arithmetical/combinatorial sentences a la Paris-Harrington, 
Friedman etc. than with respect to some sentences which only say 
something natural - through some chosen coding - about Turing 
machines etc. 

But anyway, I don't feel that there is really any substantial 
disagreement between us.  

What I have been trying to insist is only that the standard 
interpretation of Chaitin's results (among many other confusions) 
has been quite confused between:

i) the minimal c such that F cannot prove K(n) > c (which cannot, 
in general,  be effectively computed from F, and has no clear 
relation to the size or complexity of F) which is the actual limiting 
constant for F.

ii) the upper bound for c, provided effectively by Chaitin's methods, 
which is an effective function of the complexity of F.

That is, the philosophical interpretation of Chaitin's result has 
derived from completely confusing these two essentially different 
issues. 

- Panu Raatikainen