[ ] … (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 tell it which one. This system performs a computation that computes other computations. This convenient innovation is the seed of the modern, multipurpose computers we have today, on which we install and uninstall all sorts of programs. But there’s no reason that a computer has to be programmable in this way. Some jobs (including, maybe, estimating the direction of a sound from interaural time differences) require computing the solution to only one kind of problem. Church, Turing and others provided an exciting variety of ways to get solutions to the same set of problems.
The Church-Turing thesis tells us which problems are computable, but not what computation is. Church and Turing offered different models for solving problems. They got the same solutions to the same problems but by different means. That means that you don’t have to be a Turing Machine to compute. You don’t have to write down line after line, step after step, in just the way that Turing describes. You could go to Church instead. You could turn to any of the other models of computation that give the same solutions to the same problems but in different ways. What makes these all models of computation? And how do we understand the possibility that two different models could both capture the same computation – long division, say?
Even if we focus on just one model of computation, there will be many different ways to get the same solution to a problem. But if a solution is reached through wildly different steps, then intuitively different computations have been carried out. This matters tremendously for cognitive science, which cares not just about saying what computable problem the brain might be solving but also about what specific kind of procedure or computation the brain performs in solving that problem. Different computations can take different amounts of time, do things in different orders according to different causal chains, and break down in different ways (therefore calling for different medical treatments when treatment is needed).
The Churc