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

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

Date: 13 May 2004 06:56:43 -0700

Torkel Franzen <torkel@sm.luth.se> wrote in message news:<vcbsme5pup8.fsf@beta19.sm.ltu.se>...
> erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
> > "But appearances notwithstanding, this is simply wrong. In fact, there
> > is no direct dependence between the complexity of an axiom system and
> > its power to prove theorems..."
>
> > Wow! I am truly impressed! I didn't read any of Chaitin's more
> > philosophical books, just the proofs in AIT, so this comes as a shock
> > to me. I could find no errors in the proofs, and they did show that
> > there *is* a direct dependence between the complexity of a FAS and its
> > power to prove theorems (say in determining digits of Omega) as
> > defined in AIT!!!
>
> Excellent! Then you can of course respond to Raatikainen's
> criticism. Just what sort of dependence is there between the
> complexity of a formal system and its capacity to prove theorems?
> Specifically, we know that we can construct a set of axioms of
> enormous complexity that proves only a set of truths of the form
> s+t=u,

The example being the one in Raatikainen's review?

> and a set of axioms of very modest complexity that proves
> Dirichlet's theorem. What is the correlation you have in mind?

The correlation I have on my mind is digital. But let me first become
sure of your reference in "a set of axioms of enormous complexity that
proves only a set of truths of the form s+t=u". Two equivalently
complex FASs can be formally independent, maybe you have stumbled upon
that truth.

Thanks, 

--
Eray Ozkural

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 ...
    (comp.theory)