[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Miguel A. Lerma]

 > Gregory Chaitin's Omega is "the probability that a random Turing Machine 
 > (program) halts".  However, consider the following program P:
 >
 > 1. Read in nonnegative integer N
 > 2. If N=2 then Halt
 > 3. Initialize scratch value X equal to 3
 > 4. If N<X then Loop
 > 5. Double X
 > 6. If N<X then Halt
 > 7. Double X
 > 8. Go to step 4
 >
 > With a little analysis we can see that if N is in 0-1 then P loops, in 2-5 P 
 > halts, in 6-11 P loops, in 12-23 P halts, etc.  If N is random and in 0-2 
 > then the probability of P halting is 1/3, in 0-5 it's 2/3, in 0-11 it's 1/3, 
 > in 0-23 it's 2/3 etc. and in general in the range 0-M P halts with 
 > probability 1/3 if log2((M+1)/3) is an even integer and with probability 2/3 
 > if log2((M+1)/3) is odd.  Thus, the probability fluctuates between 1/3 and 
 > 2/3, and does not converge as the maximum value of N considered grows without 
 > bound.  (The same analysis applies if programs are assumed to be self 
 > contained and do not perform an initial read, for example, always beginning 
 > on  a blank tape.)
 >
 > 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.
 >
 > Charlie Volkstorf
 > Cambridge, MA

Chaitin's Omega number is not a unique number but a collection of
numbers each depending on a particular universal Turing machine T and
a (maximal) set of self-delimiting programs P (programs verifying that
none of them is a prefix of another program in P - you can get this
for instance by ending every program with an "end" instruction).
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