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 Church-Turing thesis is a (mostly informal) statement about the nature of computability. It roughly asserts that there is, up to equivalence, only one single universal concept of computability.
Slightly more in detail, the (physical) Church-Turing thesis says vaguely that what is computable in the mathematical sense of computation is precisely what is “effectively” computable (physically computable).
In interpreting this one has to be careful which concept of computation is used, there are two different main types:
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 |
Indeed, there are physical processes (described by the wave equation) which are not type-I computable (Pour-El et al. 83), but they are type-II computable (Weihrauch-Zhong 01, Weihrauch-Zhong 02, Weihrauch-Zhong 06). For more on this see at computable physics.
One then distinguishes:
The physical Church-Turing thesis: What is physically computable is also computable in the mathematical sense of computability.
The strong physical Church-Turing thesis: Every real number found by experiment in the observable universe is a computable real number.
This strong version is often phrased as “the universe is a computer” or as “digitial physics”.
On the strong physical Church-Turing thesis see SEP – Computation in Physical Systems – Is every Physical system computational? for a general account and (Waaldijk 03) for a more formal account emphasizing the role of intuitionistic/constructive mathematics.
More concretely, the kind of experiment proposed there to test whether non-computable sequences of events may appear in experiment has been claimed to have been carried out with quantum process in (CDDS 10).
General reviews include
Wikipedia, Church-Turing thesis, Digital physics
Stanford Encyclopedia of Philosophy, The Church-Turing Thesis, Computation in Physical Systems
A discussion well-informed by theoretical computability, realizability and intuitionistic(/constructive mathematics is in
Discussion of physical processes which are not type-I computable by partial recursive functions are found in
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.
Proof that these physics processes (wave equation, Schrödinger equation) are however type-II computable is in
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)
Klaus Weihrauch, Computing Schrödinger propagators on Type-2 Turing machines, Journal of Complexity
Volume 22, Issue 6, December 2006, Pages 918–935
Discussion of (non-)computability of quantum processes is in