[FOM] Status of Quantum Computing - Omega Wellfoundedness
Axiomize@aol.com
Axiomize at aol.com
Fri Oct 25 10:48:17 EDT 2002
> 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
More information about the FOM
mailing list