Church-Turing thesis


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:


  • 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)


Supplemental resources (the following are optional, but you may find them useful)


Stanford Encyclopedia of Philosophy

See also

-No Additional Notes-