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