Church–Turing thesis

Summary

The Church–Turing thesis is a claim about the informal notion of an algorithm. It says that a function on the natural numbers can be calculated by an effective method exactly when a Turing machine computes it. It is not a theorem, because "effective method" is an informal notion and cannot be the subject of a proof. It is supported by the fact that all proposed formal models of computation define the same class of functions. These models include general recursive functions, the lambda calculus and Turing machines. The thesis lets one prove that a problem has no algorithm at all by proving that no Turing machine solves it.