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. Am I being captious? Well, collections like this one do tend to be very mixed blessings, 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 rather convincing.

2 thoughts on “<em>KGFM</em> 7, 8: Computers and computation, Papadimitriou and Copeland”

  1. Several times you have complained of papers in this volume saying “this is not new” or “there is nothing new here”. But for those of us not well versed in the literature, this isn’t a helpful criticism: do these papers do a good job of summarising or explaining the extant literature on the subject.

    Obviously a review is somewhat relative to an audience, and I guess you are reviewing this book for “people like you”. That is, people who know this stuff well. But I would be interested in knowing whether these papers are well written and correct in their assertions, even if they are rehashing material that is old hat to the experts.

    Might I suggest that by assessing these papers also from a perspective of someone not au fait with the literature, you might have more scope to be more positive about them…

    1. Well, the comments so far — on the first, historically orientated part of the collection — are for “people like me” in the sense of people who are not particularly excited by the history (like most readers of the blog, I’d guess) and who want to know if there is any special reason to read these papers, life being short and must-read lists already being long.

      But I’d certainly say if a piece is a bit of terrific exposition, even if exposition of (relatively) old news. See the next post on Rindler’s paper!

Leave a Comment

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

Scroll to Top