[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.


More information about the FOM mailing list