This page is about computability of fundamental physics in the sense of computable mathematics and constructive analysis. It is not about computational physics, though of course there is a relation. For computational complexity theory in physics see at computational complexity and physics.
physics, mathematical physics, philosophy of physics
theory (physics), model (physics)
experiment, measurement, computable physics
Axiomatizations
Tools
Structural phenomena
Types of quantum field thories
constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
The following idea or observation or sentiment has been expressed independently by many authors. We quote from Szudzik 10, section 2:
The central problem is that physical models use real numbers to represent the values of observable quantities, $[...]$ Careful consideration of this problem, however, reveals that the real numbers are not actually necessary in physical models. Non-negative integers suffice for the representation of observable quantities because numbers measured in laboratory experiments necessarily have only finitely many digits of precision.
Diverse conclusions have been drawn from this. One which seems useful and well-informed by the theory of computability in mathematics is the following (further quoting from Szudzik 10, section 2)
So, we suffer no loss of generality by restricting the values of all observable quantities to be expressed as non-negative integers — the restriction only forces us to make the methods of error analysis, which were tacitly assumed when dealing with real numbers, an explicit part of each model.
In type-I computability the computable functions are partial recursive functions and in view of this some authors concluded (e.g. Kreisel 74) (and we still quote Szudzik 10, section 2 for this):
To show that a model $[$ of physics $]$ is computable, the model must somehow be expressed using recursive functions.
A similar sentiment is voiced by Geroch and Hartle:
We propose, in parallel with the notion of a computable number in mathematics, that of a measurable number in a physical theory. The question of whether there exists an algorithm for implementing a theory may then be formulated more precisely as the question of whether the measurable numbers of the theory are computable. We argue that the measurable numbers are in fact computable in the familiar theories of physics, but there is no reason why this need be the case in order that a theory have predictive power. Indeed, in some recent formulations of quantum gravity as a sum ver histories, there are candidates for numbers that are measurable but not computable.
However, in computability theory there is also the concept of type-II computable functions used in the field of “constructive analysis”, “computable analysis”. This is based on the idea that for instance for specifying computable real numbers as used in physics, an algorithm may work not just on single natural numbers, but indefinitely on sequences of them, producing output that is in each step a finite, but in each next step a more accurate approximation.
type I computability | type II computability | |
---|---|---|
typical domain | natural numbers $\mathbb{N}$ | Baire space of infinite sequences $\mathbb{B} = \mathbb{N}^{\mathbb{N}}$ |
computable functions | partial recursive function | computable function (analysis) |
type of computable mathematics | recursive mathematics | computable analysis, Type Two Theory of Effectivity |
type of realizability | number realizability | function realizability |
partial combinatory algebra | Kleene's first partial combinatory algebra | Kleene's second partial combinatory algebra |
This concept of type-II computability is arguably closer to actual practice in physics.
Of course there is a wide-spread (but of course controversial) vague speculation (often justified by alluding to expected implications of quantum gravity on the true microscopic nature of spacetime and sometimes formalized in terms of cellular automata, e.g. Zuse 67) that in some sense the observable universe is fundamentally “finite”, so that in the end computability is a non-issue in physics as one is really operating on a large but finite set of states.
However, since fundamental physics is quantum physics and since quantum mechanics with its wave functions, Hilbert spaces and probability amplitudes invokes (functional) analysis and hence “non-finite mathematics” even when describing the minimum of a physical system with only two possible configurations (a “qbit”) a strict finitism perspective on fundamental physics runs into problems (highlighted for instance in (Feynman 81, slide 15)). Precisely this kind of issue is the topic of computable analysis (“constructive analysis”, “exact analysis”) with its type-II notion of computable functions, which would therefore seem to be the right mathematical context discussing computability in fundamental (namely quantum) physics. This point is made in (Weihrauch-Zhong 02) for the wave equation.
This matters: there are solutions to the wave equation with type-I computable initial values which are not themselves type-I computable (Pour-El et al. 83). If type-I computability were the right concept of computabuility in physics, this result would show a violation of the Church-Turing thesis. But in (Weihrauch-Zhong 02) it is argued that the correct concept to use is indeed type-II computability and it is shown (Weihrauch-Zhong 02, theorem 3.2) that the solution operator to the wave equation is indeed type-II computable. The same is shown for the Schrödinger equation of quantum mechanics in (Weihrauch-Zhong 01, Weihrauch-Zhong 06) where it is found that the Schrödinger operator is computable on the Lebesgue space $L^p$ precisely for the physically relevant value $p = 2$. A similar conclusion is reached by Baez.
In the vein of type-II computability the issue specifically of computable quantum physics/quantum logic has only been further considered in (Streicher 12), where it is shown that at least a fair bit of the Hilbert space technology of quantum mechanics/quantum logic sits inside the function realizability topos $RT(\mathcal{K}_2)$.
The question whether the observable universe or at least all experiments done within are computable is part of the (strong) physical Church-Turing thesis. See there for more, and see (Waaldijk 03). Experiments showing non-computability in quantum processes have been claimed in (CDDS 10).
Decent discussion of computability in physics includes the following
Robert Rosen, Church’s thesis and its relation to the concept of realizability in biology and physics, Bulletin of Mathematical Biophysics 24 (1962), 375–393.
Konrad Zuse, Rechnender Raum, Elektronische Datenverarbeitung 8 (1967), 336–344.
Georg Kreisel, A notion of mechanistic theory, Synthese 29 (1974), 11–26.
Richard Feynman, Simulating physics with computers, talk at 1st conference on Physics and Computation MIT (1981), (talk notes by P. Birnbaum, E. Tromer: pdf)
Marian Boykan Pour-El, J. Ian Richards, Computability and noncomputability in classical analysis’, Trans. Amer. Math. Soc. 275 (1983) 539-560.
Marian Pour-El, Ning Zhong, The wave equation with computable initial data whose unique solution is nowhere computable, Math. Logic Quart. 43 (1997) no. 4, 499-509.
Douglas Bridges, Constructive mathematics and unbounded operators – a reply to Hellman, J. Philosophical Logic 24, 549–561 (1995)
Klaus Weihrauch, Ning Zhong, Is the linear Schrödinger Propagator Turing Computable? , in Jens Blanck et al (eds.) Computability and Complexity in Analysis: 4th International Workshop , CCA, Springer 2001
Klaus Weihrauch, Ning Zhong, Is wave propagation computable or can wave computers beat the Turing machine?, Proc. of the London Math. Soc. (3) 85 (2002) (web)
Frank Waaldijk, section 7 of On the foundations of constructive mathematics – especially in relation to the theory of continuous functions, 2003 (pdf, web discussion).
Klaus Weihrauch, Computing Schrödinger propagators on Type-2 Turing machines, Journal of Complexity
Volume 22, Issue 6, December 2006, Pages 918–935
Matthew Szudzik, The Computable Universe Hypothesis, in Hector Zenil (ed.) A Computable Universe: Understanding and Exploring Nature as Computation , World Scientific, 2012, pp. 479-523 (arXiv:1003.5831)
Cristian Calude, Michael Dinneen, Monica Dumitrescu, Karl Svozil, Experimental Evidence of Quantum Randomness Incomputability, Phys. Rev. A 82, 022102 (2010) (arxiv:1004.1521, web announcement)
Thomas Streicher, Computability Theory for Quantum Theory, talk at Logic Seminar Univ. Utrecht in July 2012 (pdf)
Stanford Encyclopedia of Philosophy, Computation in physics
Some general remarks on the impact of realizability (intuitionistic/constructive mathematics) on computability in physics and the Church-Turing thesis are in
A useful set of lecture notes on the mathematical background of computability and realizability is in
Andrej Bauer, Realizability as connection between constructive and computable mathematics, in T. Grubba, P. Hertling, H. Tsuiki, and Klaus Weihrauch, (eds.) CCA 2005 - Second International Conference on Computability and Complexity in Analysis, August 25-29,2005, Kyoto, Japan, ser. Informatik Berichte, , vol. 326-7/2005. FernUniversität Hagen, Germany, 2005, pp. 378–379. (pdf)
Robert Geroch, James Hartle, Computability and physical theories, Foundations of Physics June 1986, Volume 16, Issue 6, pp 533-550 (doi, PDF)
John Baez, Recursivity in Quantum Mechanics, PDF
Ye presents a constructive development of part of quantum theory and relativity theory.