Church-Turing Thesis

Every effectively computable function is computable by a Turing machine

The Thesis: Any function that can be computed by an algorithm can be computed by a Turing machine. Church (λ-calculus, 1936) and Turing (machines, 1936) independently proved their models equivalent — and equivalent to recursive functions (Kleene), Post systems, register machines, etc.

λ-Calculus

Church's model: anonymous functions, application, substitution. Church numerals encode integers: zero = λfx.x, succ = λnfx.f(nfx)

Click to evaluate

Turing Machine

Binary adder on a tape. Unary: 1ⁿ + 1ᵐ = 1ⁿ⁺ᵐ. Same function, different mechanism.

Click to evaluate

μ-Recursive Functions

Kleene's model: zero, successor, projection, composition, primitive recursion, minimization. Add(n,m) = n applications of successor to m.

Click to evaluate
All three models compute the same set of functions — provably equivalent.