[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