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.

Related Topics:
Computability theory - Alonzo Church - Alan Turing - Hypothesis

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The thesis claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It is generally assumed that an algorithm must satisfy the following requirements:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• The algorithm consists of a finite set of simple and precise instructions that are described with a finite number of symbols.
• The algorithm will always produce the result in a finite number of steps.
• The algorithm can in principle be carried out by a human being with only paper and pencil.
• The execution of the algorithm requires no intelligence of the human being except that which is needed to understand and execute the instructions.

An example of such a method is the Euclidean algorithm for determining the greatest common divisor of two natural numbers.

Related Topics:
Euclidean algorithm - Greatest common divisor - Natural numbers

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This description of algorithm is intuitively clear but lacks formal rigor, since it is not exactly clear what a "simple and precise instruction" is, and what exactly the "required intelligence to execute these instructions" is. (See for example effective results in number theory for cases well beyond the Euclidean algorithm.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Informally the thesis states that our notion of algorithm can be made precise (in the form of computable functions) and computers can run those algorithms. Furthermore, a computer can theoretically run any algorithm; that is, all ordinary computers are equivalent to each other in terms of theoretical computational power, and it is not possible to build a calculation device that is more powerful than a computer. (Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The thesis may be regarded as a physical law as it cannot be mathematically proven.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Church?Turing thesis: Church?Turing thesis ►