# Church-Turing Thesis Church-Turing Thesis, AKA * Computability Thesis * Church-Turing conjecture * Church's (hypo)thesis/conjecture on computability * Turing's thesis Church-Turing thesis is a mathematically unprovable belief that a reasonable intuitive definition of computability is equivalent to the list of provably equivalent formal models of computation, and, intuitively, what is computable by a computer program written in any reasonable PL. * Turing machine * Lambda Calculus * Post Formal System * Partial Recursive Functions * Unrestricted Grammar * Recursively Enumerable Language *Church-Turing Thesis* is a hypothesis about the nature of *computable functions* that states that a function on the natural numbers can be calculated by an effective method iff it is computable by a *Turing machine*. Before the precise definition of computable function, mathematicians often used the informal term *effectively calculable* to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability: --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mandober.gitbook.io/math-debrief/600-toc/630-computability-theory/church-turing-thesis.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.