Turing-machine model—pros and cons

7 In favor of the Turing-machine model, one can say that it's desirable to use a finite-state abstraction for a finite-state machine. Moreover, the Turing machine's simplicity and economy of description are attractive. Furthermore, it is universal in two senses: First is the Church-Turing thesis, which states that what a Turing machine can compute may be considered a universal definition of computability. (Computability on a Turing machine is equivalent to computability in the lambda calculus, a logical system formulated by Alonzo Church in 1936.) Although one cannot prove the Church-Turing thesis, it appeals to our intuitive notion of computabiliy.

8   There is also a second sense in which the Turing machine is universal: All "reasonable" machines are polynomially equivalent to Turing machines. Informally, this means that if the minimal time to compute an output on a Turing machine is T(n)for an input of size n and if the minimal time to compute an output on any other machine is S(n), then T does not grow faster than a power of S.  Therefore, one might as well use the Turing machine as the model of computation. I am, however, not convinced of the assertion that all reasonable machines are polynomially equivalent to Turing machines, but I'll defer my critique for the moment.

9 What are the disadvantages of the Turing-machine model? I believe it is not natural to use such a discrete model in conjunction with continuous mathematical mod­els. Furthermore, estimated running times on a Turing machine are not predictive of scientific computation on digital computers. One reason for this is that scientific computation is usually done with fixed-precision floating­-point arithmetic, so that the cost of arithmetic operations is independent of the size of the operands. Turing-machine operations, by contrast, depend on the sizes of numbers.

10 Finally, there are interesting computational models that are not polynomially equivalent to the Turing-ma­chine model. Consider the example of a random-access machine in which multiplication is a basic operation and memory access, multiplication, and addition can be per­formed at unit cost. Such machines go by the ungainly acronym UMRAM. This seems like a reasonable abstrac­tion of a digital computer, in which multiplication and addition on fixed-precision floating point numbers cost about the same. But the UMRAN is not polynominally equivalent to a Turing machine! However, a RAM that does not have multiplication as a fundamental operation is polynomially equivalent to a Turing machine.