[FOM] Status of Quantum Computing vis-a-vis Chomsky Hierarchy/Computing
steve at cs.clemson.edu
Wed Oct 16 10:26:35 EDT 2002
Duraid Madina writes:
> > <snip> Rogers *Theory of Recursive Functions and Effective
> > Computability*, chapter 1.
> I can't say I've seen this text, but just looking at that title I'm
> going to guess "false" anyway.
There are 10 things: (page 2)
*1. An algorithm is given as a set of instructions of finite size.
*2. There is a computing agent, usually human, which can react to the
instructions and carry out the computations.
*3. There are facilities for making, storing, and retrieving steps in
*4. Let P be a set of instructions as in *1 and L be a computing agent
as in *2. The L reacts to P in such a way that, for any given
input, the computation is carried out in a discrete stepwise
fashion, without use of continuous methods or analogue devices.
*5. L reacts to P in such a way that a computation is carried forward
deterministically, without resort to random methods or devices;
I had *3, *4, and *5 in mind in asking the question. *3 is suspect due
to entanglement and the measurement side effects. *4 is suspect due to
the "continuous methods or analogue devices". *5 is suspect due to "dice".
Rogers then goes on to ask five questions
*6. Is there to be fixed finite bound on th size of the inputs?
*7. Is there to be a fixed finite bound on the size of the set of
*8. Is there to be a fixed finite bound on the amount of "memory"
*9. Is there to be, in any sense, a fixed finite bound on the capacity
or ability of the computing agent?
*10. Is there to be, in any way, a bound on the length of a
computation? More specifically, should we require that the length
of a particular computation be always less than a value that is
"easily computable" from the input and from the set of
instructions P? To put it more informally, should we require that,
given any input and given any P, we have some idea, "ahead of
time", of how long the computation will take?
Here, I would say *8 and *9 are suspect.
D. E. (Steve) Stevenson, Department of Computer Science, Clemson
More information about the FOM