The physical Church-Turing thesis and the principles of quantum theory
From MaRDI portal
Publication:4902897
DOI10.1142/S0129054112500153zbMATH Open1279.68096OpenAlexW2962804872MaRDI QIDQ4902897FDOQ4902897
Authors: Pablo Arrighi, Gilles Dowek 
Publication date: 18 January 2013
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1102.1612
Recommendations
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- scientific article
- 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
Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Cellular automata (computational aspects) (68Q80)
Cites Work
- Non-Turing computations via Malament--Hogarth space-times
- Quantum theory: concepts and methods
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- Embedding infinitely parallel computation in Newtonian kinematics
- Experimental computation of real numbers by Newtonian machines
- Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
- Locality and information transfer in quantum operations
- More really is different
- Title not available (Why is that?)
Cited In (15)
- What is the Church-Turing Thesis?
- The stochastic thermodynamics of computation
- Semantics of quantum programming languages: Classical control, quantum control
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- An overview of quantum cellular automata
- Quantum principles and mathematical computability
- Title not available (Why is that?)
- 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)
