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.

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... entropy is a real number. ... We have been talking about Kolmogorov/Chaitin complexity all along, ... > have higher algorithmic complexity than the axioms. ... we fix the inference rules. ...
    (sci.math)
  • Re: Entropy in crystalization: up or down?
    ... available energy. ... simple, uniform, repeating structures with minimal complexity, and ... Does crystallization represent a decrease in entropy or no? ... entropy refers to the amount of energy in a system ...
    (talk.origins)
  • Re: Entropy
    ... If you look at Shannon experiment you clearly see that his definition of entropy is deeply rooted in predictability. ... You can base a definition of information complexity of a message on predictability, which itself has a lot to do with rules and exceptions. ... But the little caveat is that in the absence of knowledge about the specific rules involved, even while a message may be not very complex, you fail to model it aka. predict it well, which gives you a high entropy. ...
    (comp.compression)
  • Re: Stephen Wolfram vs. Charles Darwin on natural selection
    ... Complexity is equated with an decrease of entropy mostly because ... increasing complexity can be equated with increasing levels of order. ... falsifiable unit of selection. ... Darwinian theory, Neo Darwinists cannot see any difference at all ...
    (sci.bio.evolution)
  • Re: Stephen Wolfram vs. Charles Darwin on natural selection
    ... increasing complexity can be equated with increasing levels of order. ... When it comes to entropy, ... organism boundary. ... Natural selection may only appear to reduce complexity e.g. cave fish ...
    (sci.bio.evolution)