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:

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-

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

-Free-

Stanford Encyclopedia of Philosophy

See also

-No Additional Notes-