Church–Turing thesis

The thesis that every effectively calculable function can be computed by a Turing machine. It identifies an informal notion of calculation with a precise mathematical model, without being a theorem about all possible physical computation.

Turing machine: An abstract machine that computes by reading and writing symbols on a tape according to a finite set of rules. This is the precise computational model named in the thesis.
Church's lambda calculus: A formal system for defining functions through abstraction and application. Its functions provide a second precise account of effective computation.
Alan Turing: A British mathematician and computer scientist who introduced the abstract machine now called the Turing machine. His 1936 work gave the thesis its most influential computational model.
Physical Church–Turing thesis: The claim that every physically realizable computation can be simulated by a Turing machine, subject to suitable efficiency qualifications. It extends the classical thesis from effective procedures to physical processes.
Effective method: A finite, mechanically followable procedure that yields an answer after finitely many steps for each input. The thesis applies to functions calculable by procedures of this kind.
Partial recursive function: A function defined by recursion and composition that may be undefined for some inputs. This independently developed formal class matches Turing-computable functions.
Alonzo Church: An American mathematician who developed lambda calculus and helped establish the foundations of computability theory. His account of effective calculation preceded and helped shape the thesis.
Extended Church–Turing thesis: The claim that realistic computational models can simulate one another with at most polynomial overhead. It adds an efficiency claim absent from the classical thesis.
Computable function: A function whose values can be produced by an algorithm that halts on every input in its domain. The thesis equates effective calculability with computability in a formal model.
Universal Turing machine: A Turing machine that simulates any other Turing machine when given its description and input. Universality shows that one machine can carry out every Turing-machine computation.

Linked from 28 pages