Mike McNally writes
James A. Donald writes:
Existing physical theories show that Super Turing machines are possible in principle though very difficult to build in practice.
That's the understatement of the year.
I was referring to the proposed quantum computers.
Such machines will probably not be able to solve NP complete problems though they will be able to solve some NP problems such as factoring.
Huh?
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). -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com