Re: Raatikainen's critique of Chaitin

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

  • Next message: Mario Tanev: "Terminology question (term for 'absolute difference')" 
    Date: 4 Sep 2004 19:36:06 -0700

    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.

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

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

    --
Daryl McCullough
Ithaca, NY
  • Next message: Mario Tanev: "Terminology question (term for 'absolute difference')"

    Relevant Pages

    • Re: Raatikainens critique of Chaitin
      ... >complexity than that of the axioms, but by only an additive factor if ... the example is PA vs ZFC. ... strength of a theory and its computational complexity seems very loose. ...
      (comp.theory)
    • Re: Simplifying M theories.
      ... Perhaps you mean the axioms relativized to the predicate 'set'. ... universe, so that S maps predicates of RA to subsets of R. ... ZFC Extensionality: ...
      (sci.logic)
    • Re: question about axiomatic set theory
      ... the other which depends on set theory. ... by Hilbert in his Hilbert program: a game played with symbols ... the axioms of ZFC. ...
      (sci.math)
    • Re: How do We Know that ZF is the Axiomatization that Proves everything Provable?
      ... definitions meet specific criteria not met by ordinary axioms. ... mathematics can be expressed and proven in ZFC. ... kind of system in ZFC and thereupon prove the Pythagorean theorem, ...
      (sci.logic)
    • Re: Ada vs Ruby
      ... that for any mathematical system based upon a set of axioms there will ... This is why beyond a certain level of complexity it's helpful to use ... an interesting theoretical limitation of all software systems but it ...
      (comp.lang.ruby)