Re: Raatikainen's critique of Chaitin

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 09/02/04 

Date: 1 Sep 2004 19:25:23 -0700

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.

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

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.

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. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... Here's how you can "construct" a sequence with an undefined limiting ... Then start copying the bits of r2 into r until Qgets above c2. ... r1 again (except for an initial segment). ... So the ratio Qwill fluctuate ...
    (comp.theory)
  • Re: Cantor Confusion
    ... So, the notion of a sequence derives really from an inductive definition such as Peano's, and not from the one primitive in set theory, membership, alone. ... For any given n, the number of steps, the staircase is defined as the sequence of segment offset pairs: ... No, that is no simpler, and does not capture the direction or magnitude of any segment in a single pair. ... If this is a valid formulation of the two objects, and an explanation for Chas' counterexample to infinite-case induction, where does this fit with set theory? ...
    (sci.math)
  • Re: Compact subsets of {0,1}^N
    ... > the case where a is the empty sequence, ie a sequence of length 0: ... > T be the tree of all finite sequences a such that S_a intersect K ... > f(every finite initial segment of a) is an initial segment of f. ... each of which is a sibling. ...
    (sci.math)
  • Re: Six Simple And Reasonable Questions ...
    ... "St. Thomas the Doubter"). ... This creates a ratio for a 1,000aa system of about ... total sequence space minus the sequences that have cytochrome c ... "sequence specificity" and taking the 20th root of a number is simply ...
    (talk.origins)
  • Re: (My Review)Yeah, I watched the FMA Premium OVA Collection earlier, and...(no spoilers)
    ... tell that there was a few years between the release of the movie ... There is a live-action segment ... I thought the Chibi wrap aprty was -hilarious-. ... It's competently handled, and the "Kids" sequence is great, but except ...
    (rec.arts.anime.misc)