[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Axiomize@aol.com]

>On Tue, 15 Oct 2002, Steve Stevenson wrote:

>> 2. Does QC compute something outside Turing computable?

>No.  No reasonable model of QC computes anything that cannot be Turing 
computed.

>> I'd appreciate any comments.

>There is room for fudging in choosing the allowed set of quantum gates for a 
circuit; one could imagine a quantum gate that has Chaitin's Omega as one of 
its transition amplitudes.

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

>Steve

------
Stephen Fenner
Computer Science and Engineering
University of South Carolina
fenner at cse.sc.edu