[FOM] Status of Quantum Computing - Omega Wellfoundedness
Miguel A. Lerma
mlerma at math.northwestern.edu
Sun Oct 27 12:45:27 EST 2002
Charlie Volkstorf wrote:
> Yes. Thus Omega is not "the probability of a Turing Machine halting".
In any set probabilities are going to depend on what probability
distribution you use. In the definition of Chaitin Omega number you
start by selecting (self-delimiting) programs by choosing 0's and 1's
at random with the same probability until you get the "end" mark.
It is a perfectly natural thing to do, in fact it seems to me more
natural than using uniform probability on an increasing finite set
of elements as we often do for instance in N (natural numbers).
But 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.
> Do we know that this is not true of the number discussed by Minsky?
>
> Minsky writes: "We now define our non-computable number Ru. [u is any
> universal Turing Machine.] Ru will begin with the decimal point and, going
> to the right, its Nth digit is 1 if U halts on the Nth tape, 0 if U never
> halts on the Nth tape."
>
> In the example of Omega discussed here earlier, the "end" marker is bit 0, so
> that the Turing Machines are, in order of enumeration, {0, 10, 110, 1110, â€¦}.
> Thus the values of 2^(-|p|) are 1/2, 1/4, 1/8, 1/16, â€¦ and Omega is
> identical with Ru. Thus Ru shares the properties of Omega.
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.
I have posted this question in another list dedicated to algorithmic
complexity.
> Minsky further writes, "I think I first learned about such things from
> Hartley Rogers' lecture notes on recursive function theory at MIT around
> 1960 or so. In those days, that subject was called 'Recursive Real Numbers.'
> In any case, the subject was clearly understood in the 1956 article by
> Shannon, Moore, deLeeuw, and Shapiro in the book 'Automata Studies'."
There has been some progress since then.
Miguel A. Lerma
More information about the FOM
mailing list