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: Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 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: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 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: A Vergis , K Steiglitz , B Dickinson, The complexity of analog computation, Mathematics and Computers in Simulation, v.28 n.2, p.91-113, April 1986 [doi>10.1016/0378-4754(86)90105-9]
• 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

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory