random

[Tim Peters]

[David C. Ullrich]
> ...
> Not that readers are likely to be reading carefully enough that it's
> going to matter, but just for the sake of telling no lies: I put
> my finger on what was bothering me about what I said here.
> It's not true that the sequence of bits of Omega is recursively
> enumerable. What's true (assuming that the N-th bit is 1 if the
> N-th program halts and 0 otherwise) is that the sequence of N
> for which the N-th bit is 1 is recursively enumerable. The
> set of N for which the N-th bit is 0 is _not_ recursively
> enumerable (and hence the sequence of bits of Omega is not
> recursively enumerable.)

It's the "assuming that the N-th bit is 1 [iff] the N-th program halts"
that's off.  Omega is the probability that "a random" program halts, and it
won't take long to figure out that "N'th-bit = halts(N-th program)" doesn't
work for that (e.g., if the 0'th program happens to halt, that would imply
the halting probability is >= 1/2 across all programs -- but the 0'th
program isn't generally that smart <wink>).  Not that the number you define
there isn't interesting in its own right!  It's a classic example of a
non-computable real that can be approximated from below, and it shares that
much with Chaitin's Omega; but, IIRC, it doesn't meet the criteria for
randomness  (machine I can be related to machine I+1 in an exploitable way
s.t. halt(I) gives information about halt(I+1) -- for example, define the
encoding s.t. odd-numbered machines J merely prepend a no-op to the J-1
machine, and then halt(J) == halt(J-1), so adjacent bits in the derived sum
are strongly correlated).

Perhaps the easiest gimmick for programmers to grok is that the set of
rationals less than omega is recursively enumerable:  Chaitin gives you a
generator object g such that the loop

    while 1:
        r = g.next()

eventually generates every rational number r less than omega.  Then the
generated sequence of values r_0, r_1, .. approximates omega from below
(although only the biggest-so-far-seen are interesting), and for any real
epsilon greater than 0 there's *some* i s.t. omega - r_i < epsilon (since
every rational less than omega is eventually generated).  So a subsequence
of the r_i converges to omega.  Two results of the theory are that there's
no effective way to compute i as a function of epsilon ("you can't tell how
close you are"), yet there's no better way to compute omega than by running
that loop (you can study the implementation of g.next() all you like, but
there's no *fundamentally* better way to do it).  That last part eats at the
optimizers among us <wink>.