nLab computable physics

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.

Idea

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.

computability

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

Related concepts

• interpretation of quantum mechanics

• measurement problem

• quantum logic, quantum computation

• coordination

• p-adic physics

• hypercomputation

• constructive mathematics, geometry of physics

References

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, Schriften zur Datenverarbeitung 1, Viehweg & Sohn (1969) [doi:https://doi.org/10.1007/978-3-663-02723-2, pdf]

  English translation: Calculating Space, MIT Technical Translation, AZT-70-164-GEMIT (1970) [pdf]

  reprinted as chapter 36 of: Hector Zenil (ed.) A Computable Universe – Understanding and Exploring Nature as Computation, World Scientific (2012) [doi:10.1142/8306]

• 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)

• Douglas S. Bridges: Can Constructive Mathematics Be Applied in Physics?, Journal of Philosophical Logic 28 5 (1999) 439-453 [jstor:30226680, doi:10.1023/A:1004420413391]

• 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)

• Stephen Wolfram: A New Kind of Science, Wolfram Media (2002) [ISBN:978-1-57955-008-0, www.wolframscience.com, Wikipedia entry]

• Hector Zenil (ed.): A Computable Universe – Understanding and Exploring Nature as Computation, World Scientific (2012) [doi:10.1142/8306]

  foreword by Roger Penrose [arXiv:1205.5823]

  introduction by Hector Zenil [arXiv:1206.0376]

• 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

• Andrej Bauer: Intuitionistic Mathematics and Realizability in the Physical World, in A Computable Universe (2012) 143-157 [doi:10.1142/9789814374309_0008, pdf, webpage]

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, 16 6 (1986) 533-550 [doi:10.1007/BF01886519, pdf]

• John Baez, Recursivity in Quantum Mechanics, PDF

Ye presents a constructive development of part of quantum theory and relativity theory.

• Feng Ye, Strict Finitism and the Logic of Mathematical Applications PDF preprint