Church–Turing thesis

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 Church-Turing 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 recursively-definable 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 near-universal acceptance.


Full article ▸

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