ABSTRACT
Explication is a matter of replacing an intuitively grasped, but pre-theoretical, concept with a more exactly characterized one. The class of computable functions from natural numbers to natural numbers began to engage mathematicians’ interest in the 1920s. Kurt Godel offered the precise concept of a general recursive function, taking as basic certain ‘easy’ and familiar functions like addition and multiplication, and providing ways of combining recursive functions that one has already specified, so that one can form new ones. Alan Turing’s explication really stands out because of the way it treats the process of mechanical computation as abstractly as possible, with amazing conceptual economy. The search for a criterion of cognitive significance is of long standing. Unfortunately, for a very long time it was of dubious success. Turing, by contrast with Godel, offered a prima facie wholly different kind of explication of the notion of computable function, in terms of idealized finite-state machines.
