More Web Proxy on the site http://driver.im/

article

Classical physics and the Church--Turing Thesis

Author:

Andrew Chi-Chih YaoAuthors Info & Claims

Journal of the ACM (JACM), Volume 50, Issue 1

Pages 100 - 105

https://doi.org/10.1145/602382.602411

Published: 01 January 2003 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Cited By

Miguel-Tomé SSánchez-Lázaro ÁAlonso-Romero L(2022)Fundamental Physics and Computation: The Computer-Theoretic FrameworkUniverse10.3390/universe80100408:1(40)Online publication date: 11-Jan-2022
https://doi.org/10.3390/universe8010040
Sprevak M(2022)Not All Computational Methods Are Effective MethodsPhilosophies10.3390/philosophies70501137:5(113)Online publication date: 10-Oct-2022
https://doi.org/10.3390/philosophies7050113
Rührmair U(2022)Secret-free security: a survey and tutorialJournal of Cryptographic Engineering10.1007/s13389-021-00283-612:4(387-412)Online publication date: 2-Mar-2022
https://doi.org/10.1007/s13389-021-00283-6
Show More Cited By

Index Terms

Classical physics and the Church--Turing Thesis
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Computability

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 50, Issue 1

January 2003

100 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/602382

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2003

Published in JACM Volume 50, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
2,498
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)3

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miguel-Tomé SSánchez-Lázaro ÁAlonso-Romero L(2022)Fundamental Physics and Computation: The Computer-Theoretic FrameworkUniverse10.3390/universe80100408:1(40)Online publication date: 11-Jan-2022
https://doi.org/10.3390/universe8010040
Sprevak M(2022)Not All Computational Methods Are Effective MethodsPhilosophies10.3390/philosophies70501137:5(113)Online publication date: 10-Oct-2022
https://doi.org/10.3390/philosophies7050113
Rührmair U(2022)Secret-free security: a survey and tutorialJournal of Cryptographic Engineering10.1007/s13389-021-00283-612:4(387-412)Online publication date: 2-Mar-2022
https://doi.org/10.1007/s13389-021-00283-6
Deutsch I(2020)Harnessing the Power of the Second Quantum RevolutionPRX Quantum10.1103/PRXQuantum.1.0201011:2Online publication date: 13-Nov-2020
https://doi.org/10.1103/PRXQuantum.1.020101
Yan FVenegas-Andraca SYan FVenegas-Andraca S(2020)Introduction and OverviewQuantum Image Processing10.1007/978-981-32-9331-1_1(1-17)Online publication date: 3-Jan-2020
https://doi.org/10.1007/978-981-32-9331-1_1
Calude CCalude E(2020)The Road to Quantum Computational SupremacyFrom Analysis to Visualization10.1007/978-3-030-36568-4_22(349-367)Online publication date: 17-Mar-2020
https://doi.org/10.1007/978-3-030-36568-4_22
Bournez ODowek GGilleron RGrigorieff SMarion JPerdrix STison S(2020)Theoretical Computer Science: Computability, Decidability and LogicA Guided Tour of Artificial Intelligence Research10.1007/978-3-030-06170-8_1(1-50)Online publication date: 8-May-2020
https://doi.org/10.1007/978-3-030-06170-8_1
Copeland BShagrir O(2018)The Church-Turing thesisCommunications of the ACM10.1145/319844862:1(66-74)Online publication date: 19-Dec-2018
https://dl.acm.org/doi/10.1145/3198448
Yan SYan S(2018)Computational PreliminariesCybercryptography: Applicable Cryptography for Cyberspace Security10.1007/978-3-319-72536-9_3(143-172)Online publication date: 5-Dec-2018
https://doi.org/10.1007/978-3-319-72536-9_3
Yan SYan S(2016)Classical and Quantum ComputationQuantum Computational Number Theory10.1007/978-3-319-25823-2_2(33-58)Online publication date: 18-Mar-2016
https://doi.org/10.1007/978-3-319-25823-2_2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents