Church–Turing thesis
From The Art and Popular Culture Encyclopedia
Related e |
Featured: |
In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. 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.
See also
- Abstract machine
- Church's thesis in constructive mathematics
- Church–Turing–Deutsch principle, which states that every physical process can be simulated by a universal computing device
- Computability logic
- Computability theory
- Decidability
- Hypercomputer
- Model of computation
- Oracle (computer science)
- Super-recursive algorithm