ChurchTuringthesis

The Church–Turing thesis is a hypothesis about the nature of computability. It states that any function that can be effectively calculated by a human using a finite procedure can also be calculated by a Turing machine, and equivalently by the lambda calculus or by general recursive functions. In other words, the intuitive notion of what is computable by a procedure coincides with the formal notion captured by these models.

History: In the 1930s, Alonzo Church proposed that effectively calculable functions are precisely the lambda-definable functions, while Alan Turing introduced the Turing machine model. Independently, Stephen Kleene and others showed that the same class corresponds to general recursive functions. The Church–Turing thesis is not a mathematical theorem; it is a widely accepted identification of an intuitive notion with formal models.

Impact: It underpins the theoretical limits of computation, including undecidable problems such as the halting problem. It also anchors modern computer science, informing what is meant by an algorithm or computable function. Extensions such as the strong Church–Turing thesis address efficient simulation and physical realizability, and discussions about quantum and probabilistic computation examine whether the thesis holds under different computational resources. While quantum machines may do certain tasks more efficiently, they do not appear to compute uncomputable functions, so computability remains unchanged by these models.