Church-Turing thesis
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
The Church-Turing thesis is the informal widely-held folk belief among computer scientists that there is no informal notion of computability which cannot be computed. It is often phrased as the belief that a Turing machine — or any other Turing-complete system, such as the Lambda calculus — embodies the intuitive notion of what is effectively calculable. If true, the thesis would imply that it is impossible to devise an algorithm which cannot be expressed as a Turing machine. The thesis specifically refers to algorithms with a finite number of well-defined deterministic steps which produce the correct answer for any input in a finite amount of time; it does not apply to heuristics, unproductive loops, or unsound behaviors.
If taken at face value, the thesis would provide metaphysical justification that no algorithms of any form in our physical universe can possibly compute functions that a Turing machine cannot; the computational complexity class of the universe would be R. This is a conservative statement predating the development of wikipedia:quantum computation; today, the computational complexity class of the universe appears to be the much weaker class BQP.