Re: Raatikainen's critique of Chaitin

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

Date: 5 Sep 2004 07:52:30 -0700

Hi Daryl,

Thank you very much for your insightful comments. I think you've
cleared up things very well in your post.

daryl@atc-nycorp.com (Daryl McCullough) wrote in message news:<chdu2m013bc@drn.newsguy.com>...
> 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.

A particular inference rule can achieve this, I agree.

In AIT, we can say that the axiom "forall x, x=x" is a program that
generates all x=x in lexicographical order, to be later processed by
any inference engine of our choice. (which can do anything it wants
on the particular x=x)

I think you are basically talking about an interesting property of
Kolmogorov complexity, which is evident to beginners like us in
Kolmogorov complexity. A very small nonhalting program with k
program-size complexity can generate all strings in {0,1}*, and parts
of its output can have higher program-size complexity than k. (ie. the
output necessarily includes all Kolmogorov-random finite strings,
whose complexity goes to infinity... the additive factor I am talking
about might be infinity :( )

Maybe a better way to deal with nonhalting computations is generalized
Kolmogorov complexity which uses computability in the limit:
http://www.idsia.ch/~juergen/ijfcs2002/

I object to none of these. The problem that Chaitin does not explain
to us in intuitive terms is that this is only one *specific* inference
rule.

For instance, if the inference rule which you have picked is classical
logic, then the case about theorem proving power explained in
Raatikainen's paper does occur. But it does not hold in general!
That's why Raatikanen's argument is flawed I believe. (That is: I can
invent an inference rule that simply discards "forall x, x=x"....)
Chaitin's theory has a syntactical flavor, it completely discards
semantic concerns! That might not be as drastic a shortcoming as it
sounds I think, if you would be willing to discuss on a separate
thread. On the other hand, I do think that a theory with more semantic
sensibility might be desirable! I would welcome work on that.

I also think time should be put back into the equation. We're doing
all these timeless equations, but we are no Gods.

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

Okay. I cannot precisely see how it can be done, you may be right. And
even if we did, it may be too patchy.

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

I don't think Chaitin's theory is a good theory to reason about PA and
ZFC, elsewhere I've suggested that these are theories with too small
complexity to be handled by the asymptotic analysis of Kolmogorov
complexity. To be precise, their complexity might vanish in the bias
of a practical programming language we might use for our decompressor.

Elsewhere, I have asked for alternative measures of theorem proving
power, which might be suitable for systems like PA or ZFC. Could you
please give me some references? I would be most delighted.

So, I'm not saying that Chaitin's results can help the mundane world
of axiomatic set theory. I don't believe that is exactly the case. I
think he just points to the very limits of the whole proof business,
that's all. While we're trying to build aircraft, he's pointing to the
limits of space travel. So, it would be like using a bazooka to shoot
a fly, if we tried to apply AIT to PA, a simple axiomatic system.

Indeed, I think Chaitin has been working on limits of mind, rather
than limits of mathematics for the most part. I think working out the
limits of mind is more interesting.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... A particular inference rule can achieve this, ... Kolmogorov complexity, which is evident to beginners like us in ... limits of space travel. ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... A particular inference rule can achieve this, ... Kolmogorov complexity, which is evident to beginners like us in ... limits of space travel. ...
    (sci.math)
  • Re: Raatikainens critique of Chaitin
    ... A particular inference rule can achieve this, ... Kolmogorov complexity, which is evident to beginners like us in ... limits of space travel. ...
    (sci.math)
  • Re: What is complexity?
    ... >> complexity. ... That is still inside of Kolmogorov complexity. ... >Dawkins' proposal, on the other hand, is practical and could be put to ... >been writing for hundreds of years now. ...
    (talk.origins)
  • Re: Stephen Wolfram vs. Charles Darwin on natural selection
    ... "Incomputability of Kolmogorov complexity ... description indeed describes one organism uniquely. ... But fairly quickly I get to a unique description of Richard Norman. ...
    (sci.bio.evolution)