Re: Panu Raatikainen's review of two of Chaitin's books.

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

Date: 18 May 2004 08:14:09 -0700

In article <vcboeolkenc.fsf@beta19.sm.ltu.se>, Torkel Franzen says...
>
>erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
>> Does he not? Okay, I think you constantly believe that I engage in
>> foul rhetoric by making others say things they have not said, while I
>> think it is Raatikainen whom engages in foul rhetoric.
>
> Forget about rhetoric. Just explain in what sense there is a direct
>dependence between the complexity of a theory and its power to prove
>theorems.

Yes, it seems to me that there is something missing from Chaitin's
program of using complexity to understand incompleteness. He wants
to say that some theorems are "hard", and they can only be proved
by a "powerful" theory. But how do you quantify "hardness" or "power"?
Computational complexity alone doesn't do it, because you can concoct
extremely complex theories that only prove a subset of the sentences
of the form "x = x".

The only way that I can think of for Chaitin's connection between
complexity and power is to make it true by definition: Letting
K(T) = Kolmogorov complexity (the size of the smallest Turing
machine that can generate the theorems of T), we define
(in the case T is a subset of True Arithmetic, and S is a
true sentence in the language of arithmetic)

   hardness(S) = min { K(T) | T is a subset of True Arithmetic,
                              and T proves S }

   power(T) = max { hardness(S) | T proves S }

These definitions have the consequence that more powerful theories
can prove harder theorems, but I don't think they capture the
intuitive notion of "hardness" very well. In particular, this
definition of "hardness" makes it impossible to have a simple
sentence that is hard to prove, because every true sentence S
can be trivially proved by the theory { S }, whose power
is at most K(S). 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Panu Raatikainens review of two of Chaitins books.
    ... > can prove harder theorems, but I don't think they capture the ... > sentence that is hard to prove, because every true sentence S ... The problem is that it depends critically on the language in which axioms ... complexity, ...
    (comp.theory)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... >>dependence between the complexity of a theory and its power to prove ... > program of using complexity to understand incompleteness. ... > can prove harder theorems, but I don't think they capture the ... > sentence that is hard to prove, because every true sentence S ...
    (comp.theory)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... erayo@bilkent.edu.tr (Eray Ozkural exa) writes: ... dependence between the complexity of a theory and its power to prove ... theorems. ...
    (comp.theory)
  • Re: Raatikainens Complexity Complex
    ... generate theorems given the axiom string. ... inference are actuated by a computer program (which is another ... Each XF contributes its own program-size complexity to ...
    (comp.theory)
  • Re: Raatikainens Complexity Complex
    ... generate theorems given the axiom string. ... inference are actuated by a computer program (which is another ... Each XF contributes its own program-size complexity to ...
    (sci.math)