[FOM] Status of Quantum Computing - Omega Wellfoundedness
Axiomize@aol.com
Axiomize at aol.com
Mon Oct 21 13:30:00 EDT 2002
>> Gregory Chaitin's Omega is "the probability that a random Turing Machine
>> (program) halts". However, consider the following program P: . . .
>> The probability fluctuates between 1/3 and 2/3, and does not converge.
>> This shows that there is no "probability of halting" for program P, and
thus
>> for programs in general, and casts doubt on whether Omega is well-defined.
> Assuming that programs p in P consist of (finite) strings of 0's and 1's
and that we choose them
> randomly (bit by bit until getting the string meaning "end"), the
probability of a given program p
> in P is 2^(-|p|), where p = length of p. Then the Omega Chaitin number
(for this universal
> Turing machine T and set of programs P) equals sum of 2^(-|p|) for p in P
such that T running p
> halts, which is perfectly well defined.
> Miguel A. Lerma
But if we substitute "has an even Goedel number" for "halts", representing
"end" by bit 0 and interpret the beginning (rest) of the program as being its
Goedel number in unary notation, then from the above procedure we conclude
that the probability of a random positive integer being even is 1/4 + 1/16 +
1/64 . . . = 1/3. If the Goedel numbers include zero, then the probability
of a random nonnegative integer being even is 1/2 + 1/8 + 1/32 . . . = 2/3.
Charlie Volkstorf
Cambridge, MA
More information about the FOM
mailing list