Church-Turing thesis

From Esolang
Jump to navigation Jump to search
This article is a stub, which means that it is not detailed enough and needs to be expanded. Please help us by adding some more information.

The Church-Turing thesis states that a Turing machine (or any other Turing-complete system, such as the Lambda calculus) embodies the intuitive notion of what is "effectively calculable." It is usually interpreted to mean that it is impossible to devise an algorithm that cannot be expressed as a Turing machine. The thesis specifically refers to algorithms with a finite number of well-defined steps, that result in the correct answer for any input, and which do so in a finite amount of time.

Some take the thesis to provide metaphysical justification that no algorithms of any form in our physical universe can possibly compute functions that a Turing machine cannot. Such interpretations are well beyond the scope of the mathematics of the proof, which don't refer to physical processes.