Re: Question on Chaitin

george says...
>
>
>Torkel Franzen wrote:
>> Keep in mind the fact that whatever your definition
>> of complexity (or "entropy"), it follows that the
>> complexity of n=n, for any n, cannot exceed the
>> complexity of the axiom "for every x, x=x".
>
>That would have to hold for every binary predicate
>that actually was (axiomatically) reflexive, over
>the whole language, not just =.

I don't think Torkel's point had anything specifically
to do with equality. I think his point was that there
*is* no definition of "complexity" that has the property
that the complexity of a theorem is less than the complexity
of the axioms used to prove it. In the usual notion of
complexity (Kolmogorov), the specific theorem

n=n

has complexity approximately log(n), while the
axiom

forall x, x=x

has a complexity that is some small constant. If
n is large, then the statement n=n has a much *greater*
complexity than the axiom "forall x, x=x".

There is nothing significant about "=". Torkel could
have made the same point with an arbitrary predicate
P(x): When n is very large,

P(n)

has a larger complexity than

forall x, P(x)

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages

  • Re: Raatikainens Complexity Complex
    ... Thus I believe the Kolmogorov ... > I cannot say what effect this interpretation has on the rest of his ... stands for the axiom schema of F1. ... A1 can have high complexity. ...
    (comp.theory)
  • Re: Raatikainens Complexity Complex
    ... Thus I believe the Kolmogorov ... > I cannot say what effect this interpretation has on the rest of his ... stands for the axiom schema of F1. ... A1 can have high complexity. ...
    (sci.math)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... for every n there is an arithmetical axiom A of the form ... k+1=1+k such that the Kolmogorov complexity of A is greater than ... a direct dependence between the complexity of a formal system and its ...
    (comp.theory)
  • Re: circular Godel Phi
    ... forall for a simple theory. ... The complexity of the theory doesn't change the complexity of ... complicated properties from very simple properties, ... its meaning is uniquely determined by the meanings ...
    (sci.logic)