Re: Question on Chaitin

stevendaryl3016@xxxxxxxxx (Daryl McCullough) writes:

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

Unless there is an upper bound on the complexity of strings, which
would render the concept pointless. Indeed Chaitin himself notes as
much in the second reference I cited, and goes on to propose another
baseless principle: "One cannot prove a theorem from a set of axioms
that is of greater complexity than the axioms and know that one has
done this."

.

Relevant Pages

  • 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)
  • Re: Raatikainens Complexity Complex
    ... >>view that complexity of axiom systems (even looking ... Godel number N will either not halt, ... "to prove a twenty pound theorem, one needs twenty pounds ... I agree that twenty pounds of axioms will be enough, ...
    (comp.theory)
  • Re: Raatikainens Complexity Complex
    ... >>view that complexity of axiom systems (even looking ... Godel number N will either not halt, ... "to prove a twenty pound theorem, one needs twenty pounds ... I agree that twenty pounds of axioms will be enough, ...
    (sci.math)
  • Re: Question on Chaitin
    ... "seems to commit this confusion" ... He has nicely illustrated this distinction by the ... expressing that a particular object has a very large complexity, ... those axioms", if referring to Chaitin's theorem, seems to commit ...
    (sci.logic)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... Chaitin has also made various dubious ... > theorem cannot be derived from those axioms". ... Raatikainen's suggestion that the axiom complexity can differ vastly ... Eray Ozkural ...
    (sci.math)
Loading