[FOM] Status of Quantum Computing - Omega Wellfoundedness

Axiomize@aol.com Axiomize at aol.com
Mon Oct 21 17:44:16 EDT 2002

> Right, with that particular choice of representing programs and 
> of marking their end, the probability of a program with even 
> Goedel number is 2/3 - and the probability of odd Goedel number
> will be 1/3. Other representations will give different probability
> distributions and also different values for Chaitin Omega number.

> Miguel A. Lerma

Yes, but is the actual probability of a random positive integer being even 
(chosen with an even distribution among positive integers) 1/2?

Should the probability of halting be independent of the representation, since 
a Turing Machine's halting behavior is independent of its representation?

There are a number of problems in mathematics concerning the fallacy of a 
"random positive integer" (without an upper bound.)  For example: You are 
presented with two boxes containing unknown amounts of money, but given that 
one contains twice the amount of the other.  You are allowed to keep one, not 
knowing what either contains.  Upon choosing one, consider the effect on your 
expected amount of money if you take the other one instead.  Let N be the 
unknown amount in your current choice.  So the other box contains either N/2 
or 2N, and the expected amount in the other box is 5/4 N.  So, whichever box 
you choose, the other box has a larger expected amount.

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.

Omega is a quite arbitrary number.

Charlie Volkstorf
Cambridge, MA

More information about the FOM mailing list