The Church-Turing thesis (formerly commonly known simply as Church's thesis) says that every effectively calculable function of integers is computable by a Turing machine. In Church's original formulation (Church 1935, 1936), effective calculability is identified with definability in the lambda calculus, equivalently with general recursive functions. Claims that arbitrary physical processes can be simulated by a Turing machine are stronger physical extensions of the thesis.
The same effectively computable functions can be represented by other models of computation, such as those involving cellular automata, combinators, register machines, and substitution systems. Comparisons with quantum computing and probabilistic computing also require specifying the model and what it means to compute a result.
There are conflicting points of view about the Church-Turing thesis. One says that it can be proven, and the other says that it serves as a definition for computation. There has never been a proof, but the evidence for its validity comes from agreement among many independently developed effective models of computation. If there were a device which could answer questions beyond those that a Turing machine can answer, then it would be called an oracle.
Some computational models are more efficient, in terms of computation time and memory, for different tasks. For example, it is suspected that quantum computers can perform many common tasks with lower time complexity, compared to modern computers, in the sense that for large enough versions of these problems, a quantum computer would solve the problem faster than an ordinary computer. In contrast, there exist questions, such as the halting problem, which an ordinary computer cannot answer, and according to the Church-Turing thesis, no effective procedure can solve it in general.
The Church-Turing thesis has been extended to a proposition about the processes in the natural world by Stephen Wolfram in his principle of computational equivalence (Wolfram 2002), which also claims that there are only a small number of intermediate levels of computing power before a system is universal and that most natural systems are universal.
