[FOM] Status of Quantum Computing - Omega Wellfoundedness
Miguel A. Lerma
mlerma at math.northwestern.edu
Mon Oct 21 10:42:34 EDT 2002
> 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
More information about the FOM
mailing list