Re: Raatikainen's critique of Chaitin

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 09/05/04 

Date: 4 Sep 2004 19:36:06 -0700

Eray Ozkural says...

>So, indeed, the theorems of a theory can have higher algorithmic
>complexity than that of the axioms, but by only an additive factor if
>we fix the inference rules.

What do you mean "by an additive factor"? As has been pointed
out, the axiom "forall x, x=x" has theorems such as
1230498101239809283401923051032909283401928340912834091823049812
=
1230498101239809283401923051032909283401928340912834091823049812
which have a *much* higher entropy.

>> It doesn't imply that if theory A has higher complexity than
>> theory B, then A is a stronger theory than theory B. So
>> the connection between entropy and strength is very loose.
>
>It could be made to imply exactly that given a few more extra
>definitions I suppose, but this is not the place for that.

No, I don't think it can.

>As I said, H(A) > H(B), and still B could prove many bits of Omega,
>while A can prove exactly 0 bits, because A is written by a really
>really bad programmer, or because the input was *simply random*, with
>absolutely *no mathematical meaning*.

No, the example is PA vs ZFC. H(PA) is not much different from H(ZFC),
but ZFC is *much* more powerful. As I said, the connection between
strength of a theory and its computational complexity seems very loose. 

--
Daryl McCullough
Ithaca, NY
Loading