Recursive Functions and Computability Theory

1936: Turing, Church, and Gödel each defined 'computable' a different way - tape machines, lambda calculus, recursive functions. Within months Kleene proved all three classes were identical. The same notion, found three times.

• Gödel's incompleteness theorem uses primitive recursive arithmetic
• Proofs of NP-hardness (NP-completeness of SAT) require a notion of computability
• Dependent type systems - functions guaranteed to terminate

Three Independent Formalizations of Computability

In 1936, one of the greatest coincidences in mathematics occurred: Alan Turing and Alonzo Church independently published formalizations of the concept of 'algorithm'. Turing used tape machines; Church used lambda calculus. Stephen Kleene proved the equivalence of both approaches to Gödel-Herbrand recursive functions.

Primitive Recursive Functions

Primitive recursive functions are built from basic functions (zero, successor, projection) using three operations: composition and primitive recursion. All of them are guaranteed to terminate.

Primitive recursive functions don't cover all computable functions. The Ackermann function A(m,n) is computable but not primitive recursive: it grows faster than any primitive recursive function.

μ-Recursive Functions

The class of μ-recursive (partially recursive) functions adds the minimization operator (μ-operator): μy[f(x,y)=0] - the smallest y for which f(x,y)=0. This operation may not terminate. It extends the class to all computable partial functions.

The Church-Turing Thesis

The Church-Turing thesis: any 'effectively computable' function is recursive (and computable by a Turing machine, and by lambda calculus). This is a thesis, not a theorem - it has no rigorous proof, since 'effectively computable' is an informal notion.

The Church-Turing thesis is the foundation of all computability theory. All undecidability proofs rest on it: if a problem is not solvable by a Turing machine, it is 'in principle unsolvable' by any algorithm.

Undecidability and the Halting Problem

The halting problem: there is no algorithm that, given an arbitrary program P and input x, determines whether P(x) terminates or runs forever. Turing proved this in 1936 using the same diagonal argument.

From the undecidability of the halting problem, hundreds of other undecidable problems follow: Post Correspondence Problem, word identity in groups, program equivalence, and solvability of Diophantine equations (Matiyasevich-Robinson-Davis-Putnam theorem).

Recursive Functions and Computability: Key Takeaways

• Primitive recursive functions: built from basic operations, guaranteed to terminate
• μ-recursive functions: add minimization, give rise to partial (non-terminating) functions
• Church-Turing thesis: three formalizations of computability are equivalent
• Halting problem: no algorithm solves it for all programs (diagonal argument)
• Undecidability is a principled limitation, not overcome by speedup or quantum computers

Computability and Mathematical Logic

The connection between recursive functions and Gödel's incompleteness theorems runs deep: the Provable(n) predicate is primitive recursive, which is what enables the self-reference construction. Turing independently reached analogous results through the Entscheidungsproblem.

• ml-06 — Related lesson

Вопросы для размышления

• If HALT(P,P) is undecidable, why do antivirus programs successfully detect malware? What's the difference?
• Rice's theorem: any meaningful property of a program's behavior is undecidable. How does this affect static code analysis?
• The Busy Beaver function grows faster than any computable function. Why are its values for large n principally uncomputable?

Связанные уроки

• fl-20-church-turing