Physical Computational Complexity and First-order Logic

• Autorzy: Whyman Richard

Identyfikatory

DOI

10.3233/FI-2021-2054

• Języki publikacji: EN

Abstrakty

EN

We present the concept of a theory machine, which is an atemporal computational formalism that is deployable within an arbitrary logical system. Theory machines are intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device characterisable by a finite first-order theory machine is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine. We then develop a concept of complexity for theory machines, and prove that the class of problems decidable by a finite first order theory machine with polynomial resources is equal to 𝒩𝒫 ∩ co-𝒩𝒫.

Słowa kluczowe

EN

physical computation; computable analysis; Blum-Shub-Smale machines; hypercomputation; church-turing thesis; non-causal computation; atemporal computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 2-3
• Strony: 129--161
• Opis fizyczny: Bibliogr. 37 poz.

Twórcy

autor

Whyman Richard

• The University of Leeds, Leeds, West Yorkshire, LS2 9JT, UK

Bibliografia

• [1] Turing AM. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London mathematical society, 1937. 2(1):230-265.
• [2] Cooper SB. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN 1-58488-237-9.
• [3] Nielsen MA, Chuang IL. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000. doi:10.1017/CBO9780511976667.
• [4] Weihrauch K. Computable analysis. Springer-Verlag, Berlin, 2000. ISBN 3-540-66817-9. doi:10.1007/978-3-642-56999-9.
• [5] Blum L, Shub M, Smale S, et al. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 1989. 21(1):1-46. doi:10.1090/S0273-0979-1989-15750-9.
• [6] Hamkins JD, Lewis A. Infinite time Turing machines. The Journal of Symbolic Logic, 2000. 65(2):567-604. doi:10.2307/2586556.
• [7] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. In: Proc. R. Soc. A, volume 400. 1985 pp. 97-117. doi:10.1098/rspa.1985.0070.
• [8] Gurevich Y. Sequential abstract-state machines capture sequential algorithms. ACM Transactions on Computational Logic, 2000. 1(1):77-111. doi:10.1145/343369.343384.
• [9] Baumeler Ä, Wolf S. Computational tameness of classical non-causal models. In: Proc. R. Soc. A, volume 474. 2018 doi:10.1098/rspa.2017.0698.
• [10] Lifshitz L Landau. Fluid Mechanics. Course of Theoretical Physics. Pergamon, Oxford, 1987.
• [11] Shor PW. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 1997. 26(5):1484-1509. doi:10.1137/S0097539795293172.
• [12] Blakey EW. A model-independent theory of computational complexity : from patience to precision and beyond. Ph.D. thesis, University of Oxford, UK, 2010.
• [13] Grigorieff S, Valarcher P. Evolving MultiAlgebras unify all usual sequential computation models. arXiv preprint arXiv:1001.2160, 2010.
• [14] Newell A, Simon H. The logic theory machine-A complex information processing system. IRE Transactions on information theory, 1956. 2(3):61-79.
• [15] Horsman C, Stepney S, Wagner RC, Kendon V. When does a physical system compute? In: Proc. R. Soc. A, volume 470. 2014 p. 20140182. doi:10.1098/rspa.2014.0182.
• [16] Beggs EJ, Tucker JV. Can Newtonian systems, bounded in space, time, mass and energy compute all functions? Theoretical Computer Science, 2007. 371(1-2):4-19. doi:10.1016/j.tcs.2006.10.010.
• [17] Smullyan RM. Theory of formal systems. Revised edition. Princeton University Press, Princeton, N. J., 1961. ISBN:978-1-4008-8200-7.
• [18] Whyman R. Characterising Computational Devices with Logical Systems. Ph.D. thesis, University of Leeds, UK, 2018.
• [19] Blackburn P, de Rijke M, Venema Y. Modal logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, 2001. doi:10.1017/CBO9781107050884.
• [20] Epstein RL. Classical mathematical logic: the semantic foundations of logic. Princeton University Press, 2011. ISBN:9781400841554.
• [21] Margaris A. Successor axioms for the integers. The American Mathematical Monthly, 1961. 68(5):441-444. doi:10.2307/2311096.
• [22] Sipser M. Introduction to the Theory of Computation, volume 2. Thomson Course Technology Boston, 2006.
• [23] Apelian C, Surace S. Real and Complex Analysis. CRC Press, 2009.
• [24] Vakil N. Real analysis through modern infinitesimals. Cambridge University Press, 2011. doi:10.1017/CBO9780511740305.
• [25] Ciesielski K. Set theory for the working mathematician, volume 39. Cambridge University Press, 1997.
• [26] Bell JS. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1964. 1(3):195.
• [27] Coecke B, Kissinger A. Picturing quantum processes. Cambridge University Press, 2017.
• [28] Aharonov Y, Vaidman L. The two-state vector formalism: an updated review. In: Time in quantum mechanics, pp. 399-447. Springer, 2008.
• [29] Henkin L. The completeness of the first-order functional calculus. The journal of symbolic logic, 1949. 14(3):159-166. doi:http://dx.doi.org/10.2307/2267044.
• [30] Cobham A, Bar-Hillel Y. The intrinsic computational difficulty of functions. 1969.
• [31] Edmonds J. Paths, trees, and flowers. Canadian Journal of mathematics, 1965. 17(3):449-467. doi: 10.4153/CJM-1965-045-4.
• [32] Vergis A, Steiglitz K, Dickinson B. The complexity of analog computation. Mathematics and computers in simulation, 1986. 28(2):91-113. doi:10.1016/0378-4754(86)90105-9.
• [33] Arora S, Barak B. Computational complexity: a modern approach. Cambridge University Press, 2009. ISBN-13:9780521424264.
• [34] Blakey E. Unconventional complexity measures for unconventional computers. Natural Computing, 2011. 10(4):1245-1259. doi:10.1007/s11047-010-9226-9.
• [35] Whyman R. An Atemporal Model of Physical Complexity. In: Electronic Proceedings in Theoretical Computer Science, volume 273. 2018 pp. 39-51. doi:10.4204/EPTCS.273.4.
• [36] Nilsson NJ. Probabilistic logic. Artificial intelligence, 1986. 28(1):71-87.
• [37] Koepke P, Koerwien M. Ordinal computations. Math. Structures Comput. Sci., 2006. 16(5):867-884. doi:10.1017/S0960129506005615.