Re: Raatikainen's critique of Chaitin

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

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.

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 ...
    (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)
  • 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)