Classical physics and the Church--Turing Thesis

Abstract

Would physical laws permit the construction of computing machines that are capable of solving some problems much faster than the standard computational model? Recent evidence suggests that this might be the case in the quantum world. But the question is of great interest even in the realm of classical physics. In this article, we observe that there is fundamental tension between the Extended Church--Turing Thesis and the existence of numerous seemingly intractable computational problems arising from classical physics. Efforts to resolve this incompatibility could both advance our knowledge of the theory of computation, as well as serve the needs of scientific computing.

References

1. Blum, L., Cucker, F., Shub, M., and Smale, S. 1997. Complexity and Real Computation. Springer-Verlag, New York.
2. Church, A. 1936. An unsolvable problem of elementary number theory. Amer. J. Math. 21, 345--363.
3. Damour, T. 1990. The problem of motion in Newtonian and Einsteinian gravity. In Three Hundred Years of Gravitation, S. W. Hawking and W. Israel, Eds. Cambridge University Press, 128--198.
4. Diacu, F., and Holmes, P. 1996. Celestial Encounters: The Origins of Chaos & Stability. Princeton University Press, Princeton, N.J.
5. Feynman, R. P. 1982. Simulating physics with computers. Internat. J. Theor. Phys. 21, 467--488.
6. Gerver, J. 1991. The existence of pseudocollisions in the plane. J. Diff. Eq. 89, 1--68.
7. Misner, C. W., Thorne, K. S., and Wheeler, J. A. 1973. Gravitation. Freeman.
8. Painlevé, P. 1897. Lecons sur la théorie analytic des equations différentielles. Hermann, Paris, France.
9. Penrose, R. 1989. The Emperor's New Mind. Oxford University Press, Oxford, England.
10. Penrose, R. 1994. Shadows of the Mind. Oxford University Press, Oxford, England.
11. Saari, D. G. 1977. A global existence theorem for the four-body problem of Newtonian mechanics. J. Diff. Eq., 26, 80--111.
12. Shor, P. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484--1509.
13. Smith, W. 1993. Church's thesis meets the N-body problem. Manuscript (http://www.neci.nec.com/homepages/wds/works.html).
14. Smith, W. 1999. Church's thesis meets quantum mechanics. Manuscript (http://www.neci.nec.com/homepages/wds/works.html).
15. Steiglitz, K. 1988. Two nonstandard paradigms for computation: Analog machines and cellular automata. In Performance Limits in Communication Theory and Practice, J. K. Skwirzynski, Ed. Kluwer Academic Publishers, Dordrecht, The Netherlands, 173--192. (NATO Advanced Study Institutes Series E, No. 142.)
16. Vergis, A., Steiglitz, K., and Dickinson, B. 1986. The complexity of analog computation. Math. Comput. Simulat. 28, 91--113.
17. Turing, A. M. 1936--1937. On comutable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., Ser. 2, 42, 230--265.
18. Xia, Z. 1992. The existence of noncollision singularities in the n-body problem. Ann. Math. 135, 3, 411--468.

Index Terms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

  • Models of computation

    • Computability