KGFM 7, 8: Computers and computation, Papadimitriou and Copeland
Looking at the postings on KGFM, I've been pretty negative so far. Sorry! OK, Macintyre's paper is indeed a tour de force but is for a pretty specialized reader. Otherwise I can only really recommend Feferman's paper so far. Am I being captious? Well, collections like this one do tend to be unexciting, don't they? Blockbuster conferences invite the great and good who perhaps don't always have much new left to say, and in any case interpret their briefs in very different ways, at different levels of sophistication; and the resulting edited volumes then bung more or less everything in with little editorial control (printing papers that wouldn't make the cut in top journals). So you get collections like this one.
And now I fear I'm going to be pretty negative about (most of) the next two papers as well. I really am getting cranky in my old age. Sigh. But Christos H. Papadimitriou writes briefly on 'Computation and Intractability'. He touches on Gödel's 1956 letter to von Neumann and his prefiguring of something like the question whether P=NP which has been extensively discussed elsewhere (and there is nothing new here). And he adverts to a result about the intractability of finding Nash equilibria which is proved by a method of arithmetization inspired by Gödel: but you won't learn how or why from this paper.
Next up is a much longer paper by Jack Copeland 'From the Entscheidungsproblem to the Personal Computer – and Beyond'. Most of this is a story about the development of computing devices from Babbage to the Ferranti Mark I (complete with photos): interesting if you like that kind of thing, but utterly misplaced in this volume. But randomly tacked on is a final section which is germane: so after Feferman, you can start reading again here, with Copeland's 'Epilogue', which is indeed worth looking at.
The issue here is Gödel's 1970 note which attributes the view that "mental procedures cannot go beyond mechanical procedures" to Turing. Copeland responds not by worrying about Gödel's anti-mechanism but with evidence that Turing shared it. He cites passages where Turing criticises what he calls an "extreme Hilbertian" view and writes of mathematical intuition delivering judgements that go beyond this or that particular formal system. In fact,
Turing's view … appears to have been that mathematicians achieve progressive approximations to truth via a nonmechanical process involving intuition. This picture, in which minds devise and adopt successive, increasingly powerful mechanical formalisms in their quest for truth, is consonant with Gödel's view that "mind, in its use, is not static, but constantly developing." These two great founders of the study of computability were perhaps not quite as philosophically distant on the mind-machine issue as Gödel supposed.
Copeland's evidence seems pretty convincing, and his conclusion was news to me.
