The Church–Turing thesis (also known as computability thesis) is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

In particular, the computability of a Turing machine is identical to a von Neumann computer with sufficiently large memory.