[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Axiomize@aol.com]

> Charlie Volkstorf wrote:
>> Is "the probability of a Turing Machine halting" (assuming uniform 
>> distribution of Turing Machines) well-defined?
>> Is the "probability of program P halting" (assuming uniform distribution 
of 
>> N) well-defined?

> I do not think so, that probability would be defined as a limit that
> (as in your example) may not exist.  But in the definition of
> Chaitin's Omega number the halting probability is the limit of an
> increasing (and bounded) sequence of rationals, which always exists.

Yes.  Thus Omega is not "the probability of a Turing Machine halting".

By altering the representation of the universal Turing Machine, we arrive at 
different values for Omega, even though the set of numbers on which the 
algorithm halts is the same in each case.

>> How is Omega different (formally, please) from any other encoding of the 
>> halting predicate into a real number (e.g. Marvin Minsky, "Computation: 
>> Finite and Infinite Machines", 1967, p. 159)?

> In the extremely compact way in which the information is packed in
> Chaitin's Omega number.  Omega is algorithmically incompressible,
> Chaitin-random, Solovay-random, Martin-Lof-random...  See for
> instance:
> - Antonin Kucera and Theodore A. Slaman: "Randomness and Recursive
> Enumerability", SIAM J. Comput, Vol.31, No.1, pp. 199-211.

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

>Miguel A. Lerma

Charlie Volkstorf
Cambridge, MA
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom