Church?Turing thesis

In computability theory the Church?Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers.

Church?Turing thesis

The thesis, in Turing's own words, can be stated as:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Every 'function which would naturally be regarded as computable' can be computed by a Turing machine.

Related Topics:
Function - Computable - Turing machine

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Due to the vagueness of the concept of a "function which would naturally be regarded as computable", the thesis cannot formally be proven. Disproof would be possible only if humanity found ways of building hypercomputers whose results should "naturally be regarded as computable".

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Any computer program can be translated into a Turing machine, and any Turing machine can be translated into any general-purpose programming language, so the thesis is equivalent to saying that any general-purpose programming language is sufficient to express any algorithm.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Various variations of the thesis exist; for example, the Physical Church?Turing thesis (PCTT) states:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Every function that can be physically computed can be computed by a Turing machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This stronger statement may have been proven false in 2002 when Willem Fouché discovered that a Turing machine cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time almost surely (with respect to Wiener measure; see reference below).

Related Topics:
2002 - Willem Fouché - Brownian motion - Wiener measure

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Another variation is the Strong Church?Turing thesis (SCTT), which states (cf. Bernstein, Vazirani 1997):

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~