FOM: Re: Chaitin
Raatikainen Panu A K
Praatikainen at elo.helsinki.fi
Wed Mar 28 04:12:04 EST 2001
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
More information about the FOM
mailing list