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: