[FOM] Status of Quantum Computing vis-a-vis Chomsky Hierarchy/Computing

[Steve Stevenson]

Duraid Madina writes:
 > Steve,
 >  
 > > <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)
\quote
*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
    a computation.
    
*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;
    e.g., dice. 
\unquote

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
\quote    
*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
    instructions? 

*8. Is there to be a fixed finite bound on the amount of "memory"
    storage available?

*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?
\unquote.

Here, I would say *8 and *9 are suspect.

Best regards,

steve
----
D. E. (Steve) Stevenson, Department of Computer Science, Clemson