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.
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.)
- 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)
→ 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
- representability in arithmetic
- 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
- register machines
Supplemental resources (the following are optional, but you may find them useful)
→ Stanford Encyclopedia of Philosophy
A philosophy reference.
Location: Article "The Church-Turing thesis"
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation