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.
- Blum, L., Cucker, F., Shub, M., and Smale, S. 1997. Complexity and Real Computation. Springer-Verlag, New York. Google Scholar
- Church, A. 1936. An unsolvable problem of elementary number theory. Amer. J. Math. 21, 345--363.Google ScholarCross Ref
- 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.Google Scholar
- Diacu, F., and Holmes, P. 1996. Celestial Encounters: The Origins of Chaos & Stability. Princeton University Press, Princeton, N.J.Google Scholar
- Feynman, R. P. 1982. Simulating physics with computers. Internat. J. Theor. Phys. 21, 467--488.Google ScholarCross Ref
- Gerver, J. 1991. The existence of pseudocollisions in the plane. J. Diff. Eq. 89, 1--68.Google ScholarCross Ref
- Misner, C. W., Thorne, K. S., and Wheeler, J. A. 1973. Gravitation. Freeman.Google Scholar
- Painlevé, P. 1897. Lecons sur la théorie analytic des equations différentielles. Hermann, Paris, France.Google Scholar
- Penrose, R. 1989. The Emperor's New Mind. Oxford University Press, Oxford, England.Google Scholar
- Penrose, R. 1994. Shadows of the Mind. Oxford University Press, Oxford, England.Google Scholar
- Saari, D. G. 1977. A global existence theorem for the four-body problem of Newtonian mechanics. J. Diff. Eq., 26, 80--111.Google ScholarCross Ref
- Shor, P. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484--1509. Google ScholarDigital Library
- Smith, W. 1993. Church's thesis meets the N-body problem. Manuscript (http://www.neci.nec.com/homepages/wds/works.html).Google Scholar
- Smith, W. 1999. Church's thesis meets quantum mechanics. Manuscript (http://www.neci.nec.com/homepages/wds/works.html).Google Scholar
- 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.)Google Scholar
- Vergis, A., Steiglitz, K., and Dickinson, B. 1986. The complexity of analog computation. Math. Comput. Simulat. 28, 91--113. Google ScholarDigital Library
- Turing, A. M. 1936--1937. On comutable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., Ser. 2, 42, 230--265.Google Scholar
- Xia, Z. 1992. The existence of noncollision singularities in the n-body problem. Ann. Math. 135, 3, 411--468.Google ScholarCross Ref
Index Terms
- Classical physics and the Church--Turing Thesis
Recommendations
Physical Hypercomputation and the Church–Turing Thesis
We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that ...
Classical communication and non-classical fidelity of quantum teleportation
In quantum teleportation, the role of entanglement has been much discussed. It is known that entanglement is necessary for achieving non-classical teleportation fidelity. Here we focus on the amount of classical communication that is necessary to obtain ...
Disentanglement and decoherence from classical non-Markovian noise: random telegraph noise
We calculate the two-qubit disentanglement due to classical random telegraph noise using the quasi-Hamiltonian method. This allows us to obtain analytical results even for strong coupling and mixed noise, important when the qubits have tunable working ...
Comments