Re: Raatikainen's critique of Chaitin

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

Date: 1 Sep 2004 08:46:25 -0700

Torkel Franzen <torkel@sm.luth.se> wrote in message news:<vcbeklmctfq.fsf@beta19.sm.ltu.se>...
> erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
> > because given first n bits of Omega, you can compute all
> > n-bit programs that halt.
>
> This is indeed a property of Omega.

Yes, yes, interesting, isn't it?
 
> > Here is a definition of randomness in Kolmogorov complexity:
> >
> > A sequence x0x1x2... is Martin-Lof random if and only if there exists
> > some constant c such that
> > KP(x0x1x2...x_{n-1}) >= n-c
> > (From Alexander Shen's lectures)
> >
> > where KP(x,y) is the prefix complexity of a pair.
>
> This is not actually the definition of Martin-Löf random. And why "a pair"?

You'll have to take that issue with Alexander Shen who is a
distinguished mathematician, in my opinion, and probably has better
handle on the subject than either of us.

>
> > The definition in
> > Chaitin, AIT is different:
> >
> > A real r is Chaitin random if the information content of the initial
> > segment r_n of length n of the base-two representation of r eventually
> > becomes and remains arbitrarily greater than n: lim H(r_n) - n =
> > infinity.
>
> Here "the information content" also refers to prefix complexity. The
> two conditions are equivalent, and are also equivalent to Martin-Löf
> randomness.

Not really. Martin-Lof randomness is equivalent to weak Chaitin
random, Solovay randomness is equivalent to Chaitin random. We are not
concerned too much with the details, but I'll take the stronger def.
just in case.

> > Omega is Chaitin random. Terefore, its information content is
> > (countably!) infinite. It cannot be computed by a program less complex
> > than infinite.
>
> What definition are you using here of the information content of an
> infinite sequence?

Limit of algorithmic information content H(s) of initial segments r_n
while n->infinity obviously since we cannot expect a program to halt
and output an infinite sequence.

> Your further comments, about "finite mechanical causes", make no
> obvious sense.

I think they do. Contrast them to Daryl's explanation.

> > > What is meant by a bit being true?
> >
> > That they attain particular 0 or 1 values according to which programs
> > halt.
>
> That "A bit is true if and only if it attains particular 0 or 1
> values according to which programs halt" has no obvious meaning.

You are again snipping the bulk of my explanation, the answer is in
the parts you cut out.

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... > This is indeed a property of Omega. ... Solovay randomness is equivalent to Chaitin random. ... while n->infinity obviously since we cannot expect a program to halt ... and output an infinite sequence. ...
    (sci.math)
  • Re: Cantors diagonal proof wrong?
    ... >infinite sequence of digits ... >could only emerge from a list with at least one line enumerated by ... Omega, not Omega plus 1. ... Unsolicited bulk E-mail subject to legal action. ...
    (sci.math)
  • Re: infinity
    ... The acceptance of that axiom is an acceptance that we ... > cannot complete an infinite sequence of operations. ... We just say, for example, "let omega be the sequence ...
    (sci.math)
Loading