Church-Turing thesis

From Esolang
Jump to: navigation, 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.

It is a thesis, not a theory, by its nature; it cannot be proven any more than the claim that "there are no such things as 30-foot-long, flying, fire-breathing donkeys" can be proven.