[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Miguel A. Lerma]

 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