Re: Raatikainen's critique of Chaitin

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 09/05/04 

Date: 4 Sep 2004 19:11:28 -0700

daryl@atc-nycorp.com (Daryl McCullough) wrote in message news:<chddkh02qrv@drn.newsguy.com>...
> Eray Ozkural exa says...
>
> >H : {0,1}* -> Z^+
>
> In general, entropy is a real number. The fact that Chaitin
> defines them so that they are always integers is not very
> important.

We have been talking about Kolmogorov/Chaitin complexity all along,
that's why.

> >> The connection between entropy of a theory and strength of
> >> a theory (what it can prove) is very loose.
> >
> >Please read Theorem C in incompleteness chapter of AIT!
>
> That theorem does *not* establish anything more than a
> very loose connection between the entropy of a theory and
> the strength of a theory.
>
> What it shows is that no theory with entropy less than n
> can determine more than (approximately) n bits of Omega.
> It doesn't imply that the theorems of a theory cannot
> have higher algorithmic complexity than the axioms.

Yes, rules of inference have their own algorithmic complexity, but
that is handled in the theory. If that is the only reason, then it's
not a very good reason for the supposed "weakness" of the theorem.

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. (But we can choose any inference rule as
we like, as long as they are truth preserving, in the mathematical
sense!)

> 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.

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*. [*] I completely agree with
that. (And there are even mathematical proofs of that which are not
very hard to accomplish I suppose because we just did it.)

Regards, 

--
Eray Ozkural
[*] Can be formalized as follows, there is a random axiom string
(finite or infinite) that gives 0 bits of information about the
halting problem.