The physical Church-Turing thesis and the principles of quantum theory

DOI10.1142/S0129054112500153MaRDI QIDQ4902897zbMATH OpenOpenAlexFDO

Authors Pablo Arrighi, Gilles Dowek

Publication date 18 January 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1612

zbMATH Keywords

cellular automataquantum computing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Cellular automata (computational aspects) (68Q80)

Abstract: Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information --- and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

Recommendations

• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• scientific article; zbMATH DE number 1189116
• Around the physical Church-Turing thesis: cellular automata, formal languages, and the principles of quantum theory
• The computational status of physics
• Hypercomputation and the Physical Church‐Turing Thesis

Cites work

• scientific article; zbMATH DE number 3958700 (Why is no real title available?)
• Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
• Embedding infinitely parallel computation in Newtonian kinematics
• Experimental computation of real numbers by Newtonian machines
• Locality and information transfer in quantum operations
• More really is different
• Non-Turing computations via Malament--Hogarth space-times
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Quantum theory: concepts and methods

Cited in

(15)

• What is the Church-Turing Thesis?
• The stochastic thermodynamics of computation
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Semantics of quantum programming languages: Classical control, quantum control
• Quantum principles and mathematical computability
• An overview of quantum cellular automata
• scientific article; zbMATH DE number 1189116 (Why is no real title available?)
• An all-or-nothing flavor to the Church-Turing hypothesis
• Physical thinking and the GHZ theorem
• Deutsch's ``Quantum theory as a universal physical theory
• On the completeness of quantum computation models
• Around the physical Church-Turing thesis: cellular automata, formal languages, and the principles of quantum theory
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Free fall and cellular automata
• Classical physics and the Church--Turing Thesis

This page was built for publication: The physical Church-Turing thesis and the principles of quantum theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902897)