nLab Church-Turing thesis

Contents

Context

Physics

physics, mathematical physics, philosophy of physics

Surveys, textbooks and lecture notes


theory (physics), model (physics)

experiment, measurement, computable physics

Constructivism, Realizability, Computability

Contents

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 computabilitytype II computability
typical domainnatural numbers \mathbb{N}Baire space of infinite sequences 𝔹= \mathbb{B} = \mathbb{N}^{\mathbb{N}}
computable functionspartial recursive functioncomputable function (analysis)
type of computable mathematicsrecursive mathematicscomputable analysis, Type Two Theory of Effectivity
type of realizabilitynumber realizabilityfunction realizability
partial combinatory algebraKleene's first partial combinatory algebraKleene'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:

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

References

General reviews include

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)

Last revised on May 3, 2014 at 02:50:33. See the history of this page for a list of all contributions to it.