Re: Raatikainen's critique of Chaitin

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

Date: 4 Sep 2004 14:55:29 -0700

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.

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

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... entropy is a real number. ... >> a theory is very loose. ... have higher algorithmic complexity than the axioms. ... the connection between entropy and strength is very loose. ...
    (comp.theory)
  • Re: Fixing RNG in Microsoft Windows?
    ... >>>the crypto program is using this as the random seed or getting it from ... >> If you or anyone has any info on the relative entropy of this PRNG ... >> call to the entropy of the my seed or merely increase the strength by ...
    (microsoft.public.win2000.security)
  • Re: Fixing RNG in Microsoft Windows?
    ... > If you or anyone has any info on the relative entropy of this PRNG ... I'd be very interested to know if I make the CryptGenRandom call ... > call to the entropy of the my seed or merely increase the strength by ...
    (microsoft.public.win2000.security)