[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Axiomize@aol.com]

> The probability interpretation is not really essential, you may
> study Omega numbers without ever mentioning probability at
> all. They will still have the same properties, they are
> algorithmically incompressible, normal to all bases, etc.

If the probabilities are (1/2, 1/4, 1/8, …) then from the value of Omega we 
may infer the halting predicate.  This is the Minsky Ru case.  Program # N 
halts iff bit # N in the binary expansion of Ru is 1, independent of the 
length of its representation.  (Omega has this value when the programs have 
lengths 1, 2, 3, … e.g. the programs are {0, 10, 110, …}.)

Now consider the general Omega case, where the probabilities depend on the 
length of the representation.  Suppose the set of legal programs contains 00 
and 01, and all other programs begin with 1 (and are self-delimiting.)  Then 
if 00 halts and 01 loops, we have the same value for Omega as when 00 loops 
and 01 halts, since both 00 and 01, being of the same length, have a weight 
of 1/4.  Then we cannot infer the halting predicate and there is less 
information in the general Omega case.  Relying on the length of the 
representation introduces ambiguity when attempting to reconstruct the 
halting predicate.

> Minsky's Ru number is obviously a particular case of Chaitin's
> Omega number, but I am not sure whether every Omega number
> is a Ru number.

Since Ru contains more information than Omega in general, then I would 
conclude that they are different sets of numbers.

> Miguel A. Lerma

Charlie Volkstorf
Cambridge, MA