[FOM] Status of Quantum Computing - Omega Wellfoundedness
Axiomize@aol.com
Axiomize at aol.com
Sun Oct 27 18:11:24 EST 2002
> 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
More information about the FOM
mailing list