nLab Church-Turing thesis

Idea

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:

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

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

Related concepts

• computability

• computable physics

References

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

• Frank Waaldijk, section 7 of On the foundations of constructive mathematics – especially in relation to the theory of continuous functions, 2003 (pdf, web discussion).

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

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