Encore #6: Gödel vs Turing

And from the same collection of articles, a link to a paper that I (for once!) unreservedly praised and agreed with.

Church’s Thesis 13: Gödel on Turing (June 14, 2007)

Phew! At last, I can warmly recommend another paper in Church’s Thesis after 70 Years

Some headline background: Although initially Gödel was hesitant, by about 1938 he is praising Turing’s work as establishing the “correct definition” of computability. Yet in 1972 he writes a short paper on undecidability, which includes a section headed “A philosophical error in Turing’s work”.

So an issue arises. Has Gödel changed his mind?

Surely not. What Gödel was praising in 1938 was Turing’s analysis of a finite step-by-step computational procedure. (Recall the context: Turing was originally fired up by the Entscheidungsproblem, which is precisely the question whether there is a finitistic procedure that can be mechanically applied to decide whether a sentence is a first-order logical theorem. So it is analysis of such procedures that is called for, and that was of concern to Gödel too.)

What the later Gödel was resisting in 1972 was Turing’s further thought that, in the final analysis, human mental procedures cannot go beyond such finite mechanical procedures. Gödel was inclined to think that, in the words of his Gibbs Lecture, the human mind “infinitely surpasses the powers of any finite machine”. So, surely, there is no change of mind, just an important change of topic.

That’s at any rate what I have previously taken to be the natural view. But I confess I’d never done any careful homework to support it. Perhaps because it chimes with view I’ve been at pains to stress in various comments on this collection of articles — namely that there is a very important distinction between (1)  the “classic” Church-Turing thesis that the effectively computable functions (step-by-small-step algorithmically computable functions) are exactly the recursive functions, and (2)  various bolder theses about what can be computed by (idealised) machines and/or by minds.

And so it is very good to see that now Oron Shagrir has given a careful and convincing defence of this natural view of Gödel’s thoughts on Turing, with lots of detailed references, in his (freely downloadable!) paper “Gödel on Turing on computability”. Good stuff!

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top