James A. Donald says:
Ray writes
1) By definition, if something can be computed by a turing machine, then it is an algorithm (Lewis and Papadimitriou)
Suppose we have a spatial transform performed by light flowing through a grid. Is that an algorithm? Perhaps it is, but I am about to describe a case that will stretch your definition of algorithm rather more drastically.
Suppose I have a frog. Is that an algorithm? Obviously not. On the other hand, suppose I define something that takes an input tape and turns it into an output tape. Is that something in the space of things we are talking about? Yes. The Church-Turing thesis is that if you are talking about the space of "things that turn input tapes into output tapes and end in particular states", turing machines are capable of doing any sort of transformation other things can, although perhaps taking longer to do so. I can believe that (possibly) quantum computers are faster, but it would be truly shocking to discover that they did some things that turing machines couldn't given enough time. Perry