Re: Raatikainen's critique of Chaitin

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

Date: 2 Sep 2004 04:03:04 -0700

daryl@atc-nycorp.com (Daryl McCullough) wrote in message news:<ch60aj027as@drn.newsguy.com>...
> Eray Ozkural says...
> >
> >Torkel Franzen <torkel@sm.luth.se> wrote
> >>
> >> > Limit of algorithmic information content H(s) of initial segments r_n
> >> > while n->infinity
> >>
> >> This limit need not exist.
> >
> >Example, please?
>
> Here's how you can "construct" a sequence with an undefined limiting
> information content:
>
> First, some definitions: If r is an infinite sequence of bits, then
> r_n is the first n bits of r. H(r_n) is the minimum number of bits
> necessary to specify a Turing machine that computes r_n. Define Q(r,n)
> to be the ratio H(r_n)/n. Typically, Q(r,n) will be somewhere between
> 0 and 1.

Q(r,n) here is some normalized measure of algorithmic randomness of
initial segments of r. (But it's not very telling!)

> Okay, so pick two reals c1 and c2 such that 0 < c1 < c2 < 1. For
> example, let c1 = 1/3 and let c2 = 2/3. Next pick two reals r1 and
> r2 such that
>
> (limit n->infinity Q(r1,n)) = 0
> (limit n->infinity Q(r2,n)) = 1

r1 is a real with very low complexity.
r2 is a weak random real.

> Now, construct a third number r, as follows:
>
> 1. Copy the bits of r1 into r up until the point where Q(r,n) drops below c1.
> 2. Then start copying the bits of r2 into r until Q(r,n) gets above c2.
> 3. Then start copying the bits of r1 into r until Q(r,n) gets below c1.
> 4. etc.

Oh, yes, ingenius, Daryl, but...

> The resulting r will look like r1 for a while, then it will start looking
> like r2 (except for an initial segment), then it will start looking like
> r1 again (except for an initial segment). So the ratio Q(r,n) will fluctuate
> forever between c1 and c2, and will never converge to anything.

We are not asking the limit of Q(r,n), we are asking

lim_{n->infinity} H(r_n)

which does not seem to show the fluctuation behavior which you
describe. We can show that H(r_n) is nondecreasing. In general, H(a)
is not tightly related to string lenth, ie. |a| << |b|, H(a) >> H(b)
is possible. However, this reasoning cannot be extended to the case
for pair encoding. (as in your construction)

Let's analyze. We have H(b) << H(a), we are asking for the information
content of H(a,b). By subadditivity of algorithmic information H(a,b)
= H(a) + H(b/a) + O(1), therefore H(a) < H(a,b) even though |b| >>
|a|. Like the case for your H(r_n). (It's not hard to find the limit
of it in this case)

Example, please?

Regards, 

--
Eray Ozkural