Church–Turing thesis

An effective method supplies finitely many precise rules that can be followed without a fresh act of ingenuity at every step. Its traditional setting is idealized human calculation with paper and pencil, abstracting from shortages of paper or lifetime. An unexplained appeal to intuition is not an additional mechanical instruction.

Ordinary column addition provides a familiar example of specified local operations. By contrast, 'keep trying until the answer feels right' leaves termination and correctness unexplained. The thesis concerns what rule-governed calculation can accomplish, not whether a particular computation is fast enough or practical with available resources.

References: [1]

In the 1930s, Church proposed characterizing effective calculability through lambda-definability and recursive functions. Turing approached the subject through an abstract machine performing elementary symbol operations. These different starting points identify the same class of computable functions. Equivalence between precisely defined formalisms is established by mathematical proof.

Turing machines also have single-tape, multiple-tape and nondeterministic variants. Simulation arguments show that these variations do not change computability. This stability under changes in representation provides important support: replacing one tape with several does not make an uncomputable function computable. Simulation may nevertheless increase running time, so equal computational power does not imply equal efficiency.

References: [2] [3]

Both sides of 'lambda-definable functions are Turing-computable functions' have exact definitions. The assertion that every effective method falls within those formalisms still relates them to a prior informal concept. Treating that assertion as an ordinary theorem would first require a complete formal account of the intended notion of effectiveness.

Turing analyzed mechanical human calculation in terms of restrictions such as observing and changing only bounded information at one step. His case is more substantial than checking a handful of familiar algorithms. Yet proving that several formal models agree is not automatically a proof that every possible meaning of computation has been captured.

References: [4] [1]

The original thesis does not directly assert that a Turing machine can perfectly simulate any physical system. Stronger claims about physical computation require assumptions about permitted processes, precision and how information is obtained. Those assumptions are not supplied merely by a theorem equating formal models.

Some versions of the extended Church–Turing thesis add an efficiency requirement, often expressed through polynomial simulation overhead. This differs from asking only whether a function is computable at all. In assessing a proposed new model, one should distinguish a speed advantage, altered resource assumptions and an enlarged class of computable functions. Simply saying that it is faster than a conventional computer does not settle which claim is at issue.

References: [1] [3]