[FOM] Status of Quantum Computing - Omega Wellfoundedness
Axiomize@aol.com
Axiomize at aol.com
Sun Oct 20 17:32:51 EDT 2002
>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
More information about the FOM
mailing list