Church-Turing Thesis

The Church-Turing thesis is the hypothesis in mathematical logic and computer science that any function computable by an effective, mechanical procedure can be computed by a Turing machine, and equivalently by Alonzo Church's lambda calculus, the two formalisms having been shown to be equivalent in the 1930s. Alonzo Church proposed his version of the thesis in 1936 using lambda calculus and recursive functions, while Alan Turing independently arrived at an equivalent formulation the same year using his abstract machine model, and the two results together are treated as defining the intuitive notion of computability itself. The thesis is not a mathematical theorem subject to formal proof, since it equates a precise formal concept with an informal intuitive one, but it has withstood every alternative model of computation proposed since, including quantum computation, in the sense that none has been shown to compute a broader class of functions.