Church-Turing thesis
Summary
The Church-Turing thesis is the hypothesis that any function which can be computed (by any deterministic procedure) can be computed by a Turing machine. Equivalently, it holds that a function is recursive if and only if it is computable. While this thesis is not a precise mathematical statement, and therefore cannot be proved, it is almost universally held to be true.
Context
This concept has the prerequisites:
- Turing machines (The Church-Turing thesis references Turing machines.)
- decidability (The Church-Turing thesis is about decidability.)
- recursive functions (One formulation of the Church-Turing thesis is that a function is computable if and only if it is recursive.)
Goals
- Know the statement of the Church-Turing thesis
- Know why it is not a precise mathematical statement
- Show that Turing machines and lambda calculus are equivalent
- Show that a function is recursive iff it is computable (by some Turing-complete formalism)
Core resources (read/watch one of the following)
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
Location:
Section 3.3. "A subtheory of number theory," subsection "Church's Thesis," pages 206-210
Additional dependencies:
- representability in arithmetic
Other notes:
- The definition of recursive functions (i.e. those representable in axiomatic number theory) is different from (but equivalent to) the usual one.
→ A Course in Mathematical Logic
A graduate textbook in mathematical logic.
- Section 6.5, "Recursive functionals and functions," starting with Theorem 5.5, pages 242-247
- Section 6.7, "Church's Thesis," pages 257-259
- Section 6.8, "Recursiveness of computable functionals," pages 259-265
Additional dependencies:
- register machines
Supplemental resources (the following are optional, but you may find them useful)
-Free-
→ Stanford Encyclopedia of Philosophy
See also
-No Additional Notes-