Church-Turing thesis

From Esolang
Jump to: navigation, search

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.