Re: Raatikainen's critique of Chaitin

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

  • Next message: Randy Howard: "Re: Importance of Computer Science degree?" 
    Date: 17 Sep 2004 10:16:34 -0700

    Hi Aatu,

    Thanks for your reply. Let's get to the heart of the matter.

    Aatu Koskensilta <aatu.koskensilta@xortec.fi> wrote in message news:<ciec3h$2e2$1@phys-news1.kolumbus.fi>...
    > Since I don't understand what you mean by 'universality of algorithmic
    > complexity' I can't tell. We don't even need these 'indexing arguments'
    > to make Raatikainen's point. There are basicly two ways to establish
    > that the characteristic constant of a theory T is not a good indicator
    > of its strength in any reasonable sense: fix a theory T and vary the
    > indexing or fix an indexing and vary T. If you have qualms about the
    > former, then concentrate on the latter.

    Hmm. Okay, let's concentrate on the latter, then. Let's put that
    argument in a really simple and clear form. Is there such a thing in
    Raatikainen's paper? Which section do you think does that? I wish to
    talk very precisely from now on. [Although that does not necessarily
    mean bad formalism, just enough to be precise]

    Let's fix a universal computer U, this is nice, because it does not
    contradict with the basic way of studying asymptotic program size
    complexity. [Let's forget the former case for a moment as you suggest,
    because I do have qualms about it and Raatikainen's subsection devoted
    to showing that it is sensible is not convincing, IMO]

    So, everything we say is about asymptotic complexity. Behavior of big
    numbers.

    Now you are suggesting that we start with an FAS T, and its axiom
    string A, and vary this theory in which way? I think you would like to
    fix the inference rules as well like Chaitin, so we are going to
    change the axiom string A.

    Now, how exactly do you suggest we vary it?

    Regards, 

    --
Eray Ozkural
PS: David Bernier suggested such a construction based on PA +
individual halting problems, but it did not seem to contradict with
Chaitin's opinion.
  • Next message: Randy Howard: "Re: Importance of Computer Science degree?"

    Relevant Pages

    • Re: Raatikainens critique of Chaitin
      ... > Since I don't understand what you mean by 'universality of algorithmic ... > complexity' I can't tell. ... We don't even need these 'indexing arguments' ... > of its strength in any reasonable sense: fix a theory T and vary the ...
      (sci.math)
    • Algorithmic Randomness is Universal (Was Re: Godels Dualism ...)
      ... > program, i.e., if its program-size complexity is ... "Theorem 7.2.1 (Universality of Kolmogorov complexity): ... for all strings x. QED. ... You are wrong in saying that algorithmic randomness ...
      (comp.theory)
    • Algorithmic Randomness is Universal (Was Re: Godels Dualism ...)
      ... > program, i.e., if its program-size complexity is ... "Theorem 7.2.1 (Universality of Kolmogorov complexity): ... for all strings x. QED. ... You are wrong in saying that algorithmic randomness ...
      (comp.theory)
    • Algorithmic Randomness is Universal (Was Re: Godels Dualism ...)
      ... > program, i.e., if its program-size complexity is ... "Theorem 7.2.1 (Universality of Kolmogorov complexity): ... for all strings x. QED. ... You are wrong in saying that algorithmic randomness ...
      (comp.theory)
    • Re: [linux-pm] Bug in PCI core
      ... reflects the state of the device to userspace, reduces complexity, and ... could potentially save some memory per PCI device instance. ... And then you can fix the applications it breaks, ...
      (Linux-Kernel)
    Loading