Church's thesis

The Church-Turing thesis (formerly commonly known simply as Church's thesis) says that any real-world computation can be translated into an equivalent computation involving a Turing machine. In Church's original formulation, the thesis says that real-world calculation can be done using the lambda calculus, which is equivalent to using general recursive functions. The Church-Turing thesis encompasses more kinds of computations than those originally envisioned, such as those involving cellular automata, combinators, register machines, and substitution systems. It also applies to other kinds of computations found in theoretical computer science such as quantum computing and probabilistic computing.

cellular automaton | Church-Rosser theorem | Church's theorem | combinator | computable function | decidable | lambda calculus | mobile automaton | principle of computational equivalence | register machine | substitution system | Turing machine | universality | universal Turing machine