James A. Donald writes:
I was referring to the proposed quantum computers.
Since such machines do not operate algorithmically
This statement is exactly wrong. Such machines *define* a class of algorithms.
I recommend that you read the following paper.
E. Bernstein and U. Vazirani, {\it Quantum Complexity Theory}, Proc. 25th ACM Symp. on Theory of Computation, pp. 11--20 (1993).
James, without reading the paper, can you tell me why the following argument is incorrect? 1) By definition, if something can be computed by a turing machine, then it is an algorithm (Lewis and Papadimitriou) 2) a quantum computer can be simulated by a TM with exponential slowdown. (claimed by you on the Extropians list, but also claimed by Feynmann I believe, not about qm computers, but qm systems in general) then by (1) and (2), it follows that 3) quantum computers are algorithmic (if not, it would contradict 2) and possibly 1) It doesn't matter how slow the turing machine runs the simulation because we allow an arbitrary time along with the infinite tape to complete the computation. -Ray