Maybe it's a man bites dog thing: One cannot write an article that says, yes, Turing machines capture computation and fully describe algorithms. But I can use this weblog to say that.
Blass and Gurevich ask "What is an algorithm?" From their introduction: It is often assumed that the Church-Turing thesis settled the problem of what an algorithm is. That isn't so. The thesis clarifies the notion of computable function. And there is more, much more to an algorithm than the function it computes. The thesis was a great step toward understanding algorithms, but it did not solve the problem what an algorithm is.
Why not? The paper goes on to discuss the meaning of the Church-Turing thesis and some scenarios where they claim the Turing machine fails to capture algorithms.
- Interactive Algorithms: A broad class containing randomized algorithms, nondeterministic algorithms and asynchronous algorithms. All of these can be simulated on Turing machines and in any case the actual interaction process is always modeled by an algorithm easily implementable on a Turing machine.
- Computing with Abstract Structures: Turing machines have no problems dealing with abstract structures given a logic that describes them. Hidden parallelism is easily simulatable.
- Non-discrete computations: Yes, a finite Turing machine cannot model arbitrary real numbers. But a Turing machine can simulate any process involving real numbers to a greater precision that any physical instrument can hope to measure.
No comments:
Post a Comment