 a rough idea, the function 3 + (14 – x) can be defined as a sum, 3 + y, where y itself is defined as a subtraction, 14 – x. To determine what 3 + (14 – x) equals, when x = 6, one first solves for 14 – 6, and then adds that solution to 3, giving 11. The idea is to break up the problem into its smallest chunks, solving it chunk by chunk. Church proposed that a mathematical problem is computable just in case it can be expressed within his sparse language for defining functions in terms of more basic functions. For him, problemsolving involves giving an explicit definition of the problem, and then following that definition to its conclusion.
Turing’s model of computation emphasises rote rule-following. Remember how, when doing long division or solving for x, you would write one line and then, following a rule you were taught, you would write down another line underneath it that was based on the previous line, and so on until the last line you wrote gave the solution? Sometimes we felt entitled to skip a step or two, but the teacher would insist that you must ‘Show your work!’ Turing took this to the extreme. He defined a system of rules or constraints for writing one line based on a previous line, in which you could see all the work down to the last, minute detail, so that your teacher could not credibly ask you to show any more.
Suppose you start with a line of symbols expressing the problem to be solved:
… 21 x 3 = ? …
and you need to get to the final line expressing the solution:
… 63 …
Imagine you are writing everything down on graph paper, with no more than one item or symbol per square. You have an instruction manual telling you what to do at each step of the computation. You always start at a particular line, in a particular square on your notebook, and you handle only one square per step. Steps in the instruction manual say that, if the current square with which you are dealing contains such-and-such, then either erase that item from the square, leaving a blank spot in its place:
… 21 x 3 = [?] …
… 21 x 3 = [ ] … (where ‘[ ]’ indicates the square in the notebook with which you are dealing)
or enter so-and-so into the square (if it is blank):
… 21 x 3 = [ ] …
… 21 x 3 =  …
or move to an adjacent square:
… 21 x 3 =  …
… 21 x 3 = 6 [ ] …
Turing’s idea was that nobody who watches a solution get churned out in this way could reasonably ask for more work to be shown. These rules or constraints on how to solve a problem define what is called a ‘Turing machine’: a system that shows all its work. The term ‘Turing machine’ refers first and foremost to an abstract mathematical object or system, a set of constraints on how one line might be transformed into another, rather than to the physical devices that we build to embody these constraints. Turing proposed that a mathematical problem is computable just in case the expression of that problem can be transformed into an expression of its solution under these constraints.
Miraculously, the set of mathematical problems that can be defined and solved in Church’s language turns out to be exactly the same set of problems that can be solved by a Turing machine. Bolstered by this convergence, the Church-Turing thesis is that the set of problems that can be computed are just the set of problems that can be solved either by a Turing machine or that can be defined within Church’s calculus. In fact, there are many models besides Church’s and Turing’s, including certain types of artificial neural networks, that are capable of giving solutions to exactly the same set of problems.
Church-Turing tells us which problems are computable, but not what computation is
One of Turing’s great achievements was to show how a single ‘universal Turing Machine’ could be programmed to perform different computations. For any given problem, one can design a Turing machine with a custom-crafted instruction manual for solving that problem. Turing went a step further and showed how to make a Prime Mover of a machine, the instruction manual of which could guide you in performing any computation, so long as you te