[FOM] Status of Quantum Computing vis-a-vis Chomsky Hierarchy/Computing
Steve Stevenson
steve at cs.clemson.edu
Tue Oct 15 15:45:48 EDT 2002
I'm a novice at the QC thing, but the following questions occurred to
me.
1. QC would apparently fail on several of the restrictions on
"computing abstractions", particularly those in Rogers *Theory of
Recursive Functions and Effective Computability*, chapter 1.
True or False?
2. Does QC compute something outside Turing computable?
If so, what is the simplest example?
I'd appreciate any comments.
best,
steve
More information about the FOM
mailing list