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)
  • Re: [opensuse] Systemd and fstab
    ... their own DHCP or their own DNS server. ... Hard coding things is simply a guaranteed way for them to break sooner or later, and when it does, the unusualness of hard coding something will waste the time of the guy who gets called in to fix it, or simply be beyond them utterly since so many local IT guys are so bad. ... And automatic/dynamic things may break sometimes because the extra complexity means more opportunities to break. ...
    (SuSE)
  • 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)