Re: Raatikainen's critique of Chaitin

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

Date: 5 Sep 2004 06:41:26 -0700

Torkel Franzen <torkel@sm.luth.se> wrote in message news:<vcbeklh6y6o.fsf@beta19.sm.ltu.se>...
> erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
> > 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.
>
> The complexity of n=n goes to infinity with n.

It can, yes.

Regards, 

--
Eray Ozkural

Relevant Pages

  • 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)
  • 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: Raatikainens critique of Chaitin
    ... incompleteness theorems in Chaitin's work. ... that there is a model for Leibniz's infinite sequences of reasons. ... Omega, a number which is meaningful, yet random. ... INFINITE COMPLEXITY. ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... incompleteness theorems in Chaitin's work. ... that there is a model for Leibniz's infinite sequences of reasons. ... Omega, a number which is meaningful, yet random. ... INFINITE COMPLEXITY. ...
    (sci.math)