> One has long heard rather routinely -- often in support of
>Church's Thesis or just as a remarkable fact -- that Church, Turing,
>Kleene, Post, . . each set out to give an informal analysis of
>"computable function", and each ended characterizing a class equivalent
>to the recursive functions.
> Reading through the relevant papers in M.Davis' anthology The
>Undecidable, I am struck by how far from the truth this
>characterization of intentions seems. If they were _not_ all (in some
>sufficiently strong sense) consciously intending to analyze "computable
>function" -- WERE THEY??? --, then what significance is properly
>attached to their coming to "the same class" of functions?
>
Since the very term "computable" seems to have been invented by Turing and
as a defined term, this formulation is, at the least, careless. What has
been said often, and is perfectly correct, is that Church, Turing, Gödel,
and Post (not Kleene) each raised the question of providing a precise
formulation for the informal notion of function (or set or relation) for
which there exists a process that in a finite number of effective
well-defined automata-like steps will provide the answer for a given
argument. And the proposed (or suggested, in the case of Gödel) answers,
although formally quite different, did turn out (remarkably) to be equivalent.
This informal notion had been in common use among mathematicians: the
process for testing a linear Diophantine equation for solvability, the
Entscheidungsproblem for first-order logic, Hilbert's tenth problem. The
informal notion was perfectly serviceable for noting that particular
proposed "algorithms" were of this character. It was only when a proof is
sought that no such process exists (that some specific problem is
"unsolvable") that a precise characterization becomes important.
Martin Davis