What is the Church-Turing thesis?

The Church-Turing thesis states that any computable function can be computed by a Turing machine. “Computable” informally means that a human using pen and paper could in principle follow a well defined sequence of steps (an “algorithm”) to arrive at the function value. A Turing machine is a particular mathematical model of a simple computer that reads and writes symbols on an infinite tape and changes state based on those symbols. So the thesis says that this model encompasses all of our informal idea of “computation”.

Further reading:

• The Church-Turing thesis on Wikipedia

• The Church-Turing thesis on the Stanford Encyclopedia of Philosophy.