Definition
The Church-Turing thesis is the hypothesis that every function that can be computed by any effective procedure (a procedure that proceeds by a finite, mechanical, well-defined series of steps) is computable by a Turing machine. The thesis is supported by the equivalence of multiple independently-discovered models of computation: Turing machines, lambda calculus, recursive functions, register machines, Markov algorithms.
Why it matters
How it works
The thesis is supported by demonstrating that independently-defined notions of computation all characterize the same class of functions. Church's lambda calculus (1936) and Turing's machines (1936) were shown equivalent within a year. Subsequent models — register machines, recursive functions, cellular automata, modern CPU instruction sets — have all proven equivalent or weaker. The convergence is strong empirical evidence that "computable" has a definite mathematical meaning these models capture.