A Continuous Model of Computation

MAY 01, 1999

Physicists should consider an alternative to the Turing‐machine model of computation.

Joseph F. Traub

A central dogma of computer science is that the Turing‐machine model is the appropriate abstraction of a digital computer. Physicists who’ve thought about the matter also seem to favor the Turing‐machine model. For example, Roger Penrose devoted some 60 pages of a book to a description of this abstract model of computation and its implications. I argue here that physicists should consider the real‐number model of computation as more appropriate and useful for scientific computation.

References

1. R. Penrose, The Emperor’s New Mind, Oxford U. P., Oxford (1989).
2. A. M. Turing, Proc. London Math. Soc. 42, 230 (1937).https://doi.org/PLMTAL
3. J. F. Traub, G. W. Wasilkowski, H. Woźniakowski, Information‐Based Complexity, Academic Press, New York (1988).
4. J. F. Traub, A. G. Werschulz, Complexity and Information, Cambridge U. P., Cambridge, England (1998).
5. J. von Neumann, Collected Works, V. A. Taub, ed., Macmillan, New York (1963).
6. L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer‐Verlag, New York (1998).
7. A. G. Werschulz, The Computational Complexity of Differential and Integral Equations: An Information‐Based Approach, Oxford U. P., Oxford (1991).
8. A. S. Nemirovski, D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley‐Interscience, New York (1983).
9. K. Sikorski, Optimal Solution of Nonlinear Equations, Oxford U. P., Oxford (1999).
10. E. Novak, Deterministic and Stochastic Error Bound in Numerical Analysis, Lecture Notes in Mathematics, No. 1349, Springer‐Verlag, New York (1988).
11. L. Plaskota, Noisy Information and Computational Complexity, Cambridge U. P., Cambridge, England (1996).
12. S. Paskov, J. F. Traub, J. Portfolio Management, 22, 113 (1995).
13. I. Sloan, H. Woźniakowski, J. Complexity 14, 1 (1998).https://doi.org/JOCOEH
14. A. Papageorgiou, J. F. Traub, Computers in Physics 11, 574 (1997).
15. B. Keister, Computers in Physics 10, 119 (1996).
16. G. W. Wasilkowski, H. Wozniakowski, J. Math. Phys. 37, 2071 (1996).https://doi.org/JMAPAQ
17. M. B. Pour‐El, J. I. Richards, Computability in Analysis and Physics, Springer‐Verlag, New York (1988).
18. A. G. Werschulz, Numer. Func. Anal. 9, 945 (1987).

More about the Authors

Joseph F. Traub. Columbia University, New York City.