
related topics 
{math, number, function} 
{theory, work, human} 
{system, computer, user} 
{math, energy, light} 

In computability theory, the Church–Turing thesis (also known as the ChurchTuring conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis ("thesis") about the nature of functions whose values are effectively calculable; i.e. computable. In simple terms, it states that "everything computable is computable by a Turing machine."
Several attempts were made in the first half of the 20th Century to formalize the notion of computability:
 American mathematician Alonzo Church created a method for defining functions called the λcalculus,
 British mathematician Alan Turing created a theoretical model for a machine that could carry out calculations from inputs,
 Church, along with mathematician Stephen Kleene and logician J.B. Rosser created a formal definition of a class of functions whose values could be calculated by recursion.
All three computational processes (recursion, the λcalculus, and the Turing machine) were shown to be equivalent—all three approaches define the same class of functions.^{[1]}^{[2]} This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Informally the Church–Turing thesis states that if some method (algorithm) exists to carry out a calculation, then the same calculation can also be carried out by a Turing machine (as well as by a recursivelydefinable function, and by a λfunction).
The Church–Turing thesis is a statement that characterizes the nature of computation and cannot be formally proven. Even though the three processes mentioned above proved to be equivalent, the fundamental premise behind the thesis—the notion of what it means for a function to be "effectively calculable" (computable)  is "a somewhat vague intuitive one".^{[3]} Thus, the "thesis" remains an hypothesis.^{[3]}
Despite the fact that it cannot be formally proven, the Church–Turing thesis now has nearuniversal acceptance.
Contents
Full article ▸


related documents 
Mathematical proof 
Alfred Tarski 
Georg Cantor 
Set theory 
Structured programming 
Vacuous truth 
Objectoriented programming 
Finite set 
Imaginary unit 
Multiplication 
Exponentiation by squaring 
Relational database 
Quadratic equation 
General linear group 
Busy beaver 
Operator 
Control flow 
Riemannian manifold 
Communication complexity 
Semidirect product 
Monoid 
Exponential function 
Lie algebra 
Interpolation 
Abstraction (computer science) 
Set (mathematics) 
Polyomino 
Stochastic process 
Metric space 
Dylan (programming language) 
