[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