nLab
Church-Turing thesis

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

Discussion of physical processes which are not type-I computable by partial recursive functions are found in

Proof that these physics processes (wave equation, Schrödinger equation) are however type-II computable is in

Discussion of (non-)computability of quantum processes is in