[FOM] Status of Quantum Computing - Omega Wellfoundedness
Stephen Fenner
fenner at cse.sc.edu
Tue Oct 22 11:32:42 EDT 2002
>
> We must be careful when considering a "random positive integer". In the case
> of the probability of a random positive integer being even, we can see these
> numbers as consisting of an infinite number of sets of two numbers, {1,2},
> {3,4}, . . . and we are choosing a random set and then a random element of
> that set. The choice from among the infinite number of sets is irrelevant,
> and so we have a well-defined probability of 1/2. No such similar analysis
> is possible for the halting behavior of Turing Machines.
>
Whoops, I guess I did it wrong ;-). I divided the natural numbers into
sets of three numbers -- {2,1,3}, {4,5,7}, {6,9,11}, {8,13,15},
{10,17,19}, {12,21,23}, ..., so I got a well-defined probability of 1/3 of
a number being even.
The actual value of Omega certainly depends on what probabilities are
assigned to what Turing machines. Once those probabilities are set, Omega
is certainly well-defined. But for the purposes of our discussion, it
does not really matter how they are set; whatever Omega we get will be
equivalent to the Halting Problem.
Steve
More information about the FOM
mailing list