# Church-Turing Thesis

https://en.wikipedia.org/wiki/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:
