random

[Tim Peters]

[David C. Ullrich]
> Um, actually I'm pretty sure that Omega _is_ what I said it is, and
> is also what you say it is.

I'm not <wink>.

> ...
> The first thing you need to note is that "probability that a random
> program halts" is _meaningless_ until we have specified how we are
> _choosing_ our "random program".

Sure.

> ...
> Ok. So Omega is the probability that a "random program"
> halts. This is one of those things I mentioned earlier:
> you read people talking about Chaitin's stuff and you
> say "what??", then you read what Chaitin actually wrote
> and you're relieved to see he included the details:
>
> Yesterday I looked at that link you provided and I
> saw Chaitin define Omega as the probability that a
> random program halts. My first reaction was that
> of course that's meaningless until you specify
> how you _select_ your "random program" (more
> precisely but less intuitively, until you specify
> what distribution on the space of all programs
> you are referring to.) But I read on:
>
> Chaitin is very well aware of everything I just
> said. Although he did not explain why he needed
> to do so, he _did_ "specify" what distribution
> he had in mind. Even though it was just a survey
> article - he knew I was going to be reading it
> someday. He says something like this (um, I may
> not get the details the same because I just skimmed
> it, I'm pretty sure he says something like this):
>
> There are countably many Turing machines. Enumerate
> them as T1, T2, ... . Now perform an experiment:
> Flip a coin. If it's heads then let T = T1.
> If it's tails flip again and if it's heads let T = T2.
> If it's tails flip again and if it's heads let T = T3.
> etc. With probability one we eventually get a head,
> so we have in fact chosen a random Turing machine T,
> with a well-defined distribution. Now Omega is the
> probability that T halts.

Chaitin's construction is actually based on the bit-length p of programs P.
A specific program P of bit-length p that halts contributes (additively)
1/2**p to Omega -- all programs of length p carry the same weight.  You may
object that there are 2**p programs of length p alone, so that this isn't
well-defined (i.e., that the programs of length p alone *may* contribute
2**p*(1/2**p) = 1 to the total, and that the sum over all P may be
unbounded).  Indeed, that was a long-standing hang-up!  "The trick" is that
Chaitin's twist on universal Turing machines requires "self-delimiting"
programs:

    A key technical point that must be stipulated in order for Omega
    to make sense is that an input program must be self-delimiting:
    its total length (in bits) must be given within the program itself.
    (This seemingly minor point, which paralyzed progress in the field
    for nearly a decade, is what entailed the redefinition of
    algorithmic randomness.)
    ...
    If programs were not self-delimiting, they could not be constructed
    from subprograms, and summing the halting probabilities for all
    programs would yield an infinite number. If one considers only self-
    delimiting programs, not only is Omega limited to the range between
    0 to 1 but also it can be explicitly calculated ``in the limit from
    below.''

IOW, there are slippery subtleties here (subtle enough to trip up serious
researchers for years) -- if you want to pursue this, it's better to stop
guessing at the gaps in popular overviews and go to the sources.  The way he
actually approximates Omega from below is to compute the values of omega_n()
for increasing n, where for a fixed n omega_n() looks at all programs P of
bitlength <= n, and for each one that halts within n seconds, adds
1/2**len(P) to a running total (where len(P) is my spontaneous <wink>
notation for the bitlength of P).  This gives, for increasing n, a
non-decreasing sequence of rationals that converge to Omega (but with a
non-computable convergence rate).

The relation to coin-tossing is this:  *each* time he flips a coin he
appends a 0 or 1 bit (depending on whether heads or tails comes up).  The
coin-tossing stops when the program is complete; the "self-delimiting"
business is crucial here, else you couldn't know when to stop; then there
are technical details about strings that aren't well-formed programs, etc.
But the finer a point you want to draw the more the details become
important, and I think we're already beyond what Usenet is any good for.

> ...
> The previous paragraph is a precise/rigorous
> specification of "Omega is the probability that
> a random program halts"

It's some sort of probability measure, yes, but not Chaitin's.

> (except it doesn't quite pin down what Omega _is_ since it does
> not specify exactly what order we put the Turing machines in at
> the start. To actually _define_ the sequence T1, T2,... we'd need
> to get into details of the syntax we were using to define TM's.)

Yes, and "Chaitin's constant" too is really a function of the specific
universal Turing machine in question.  Without qualification, it usually
refers to the Omega of a specific UTM he coded in Lisp and published.
However, Chaitin's defn doesn't involve a bijection between natural numbers
and machines, except in the incidental sense that programs are viewed as
bitstrings which *could* be viewed as integers -- but the defn makes no use
of that, only of the *lengths* of programs, and those are independent of
arbitrary orderings.

> ...
> I don't think so. And in any case if you _do_ choose your program
> by flipping a coin as above that specifies a distribution, and with
> that distribution the probability that a random program halts _is_
> a number with n-th bit = 1 if and only if the n-th TM halts.

Can only repeat that it's a classic example, and, again, IIRC it doesn't
meet the criteria for randomness.  Could be I'm wrong about that, but this
is far enough removed from what I'm supposed to be doing right now that I'm
not going to go searching one way or the other.  If you do, let me know what
you find out.

> ...
> (And in fact when I think about how to do that
> and I think about how one would "naturally"
> order the TM's it's not clear to me that such
> non-randomness does not creep into Omega
> defined using a "natural" ordering...)

As above, Chaitin's defn. is independent of ordering.

> If I have the "definition" straight (and
> note that nothing I've said contradicts
> what you said about the definition!) then
> the bits of Omega are not going to be much
> use for an RNG.
> ...

I agree with the conclusion regardless.

> But it turns out that Omega _does_ solve a
> _different_ practical problem! What's the
> other pressing problem? Determining which
> reals have exact floating-point representations.
>
> Thm1. Omega does not have an exact representation
> in finite-but-unbounded-precision floating point.
>
> Thm2. Thm1 is all you can say about Omega, given
> the definition above: If x is any real (between
> 0 and 1) and x does not have an exact representation
> in finite-but-unbounded-precision floating point
> then there is an ordering T1, T2,... of our
> Turing machines that makes Omega = x.

Since it's not a computable ordering, I'm not sure "solves" was the right
word <wink>.  Note that recent results have shown that every non-computable
*random* real (in (0, 1)) is the (Chaitin-style) Omega for some
self-delimiting UTM.  That's a paraphrase.  A precise statement requires
pages of defns, and again people interested enough should go the sources (I
gave a good link earlier in this thread).

> ...
> (Devil's advocate: But if Omega can be 0.10101010...
> then how can it be incompressible? You're not actually
> saying Chatin's wrong about that, are you?

No.  I believe instead that there's no self-delimiting UTM (etc -- insert
paragraphs of defns here) s.t. 0.1010... is its Omega.  All Omegas are known
to be random.

>> 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.

> Yup. Doesn't contradict the statement that the n-th bit is 1 if and
> only if the n-th program halts.

Right:  that part wasn't for your benefit <wink>, it was for others who may
not have known what "recursively enumerable" means.  What I said in that
part applies to *any* "computably enumerable (c.e.) real" == any real number
such that the set of all rationals less than it can be generated.  Your
number and Omega are both c.e., so that part applied equally to both.  For
that matter, the real number 6.0 is also c.e..

The later points about the convergence rate being non-computable and that
there's no "fundamentally better" way to compute the limit don't follow from
that much alone.  That's why I called them "two results of the theory"
(referring (too) obliquely to Chaitin's theory).