I recently bought David Lewis’ *Papers in Philosophical Logic* and have been reading some of the essays recently, starting with the shorter ones. I hadn’t remembered how engaging his writing style is.

Anyway, I should probably read Roger Penrose again some time, but from what I remember of his theses in *The Emperor’s New Mind* and *Shadows of the Mind*, it looks like they were pretty soundly refuted long before he wrote the books. This was by Lewis in his two papers “Lucas against Mechanism” and “Lucas against Mechanism II”. The first one just makes the point that the inference rule from a theory to its consistency statement is in general infinitary, and thus can’t clearly be run in general. But the second one faces a tougher argument, because of the way Lucas seemed to moderate his position. (I haven’t actually read Lucas, or even heard of him before reading these two papers by Lewis, but it sounds like he was advocating the same position that Penrose did, that our ability to recognize Gödel statements proves that humans are not Turing machines.)

In the second paper, Lewis phrases Lucas’ argument as a challenge to the mechanist to produce a Turing machine that generates exactly the set of truths that Lucas recognizes to be true. Lucas can then find the Gödel statement of this machine and recognize it to be true, which shows Lucas not to be this actual machine. But Lewis points out that since this allows Lucas to respond to challenges, the machines proposed must also be the sort that can respond to challenges. So if the mechanist proposes that Lucas is the machine M, then Lucas might either be responding with the Gödel number of the machine M, or with the Gödel number of the machine M would turn into in response to a challenge with the number M. But Lewis claims that there are many machines that make the former response to any true accusation that they are M, and there are many machines that (falsely) make the latter response to any true accusation that they are M, so Lucas’ ability to give such a response doesn’t prove him not to be a machine.

This is where I would like a bit more clarification. At first Lewis’ claim sounded ridiculous, because it sounded like his response to the former was a machine that takes any input and responds with the Gödel number for that input, which sounds impossible to me. (Maybe I’m wrong about that?) Now I think that he actually meant something more like a machine that gives the same response to any challenge, and this response just happens to be its own Gödel number. After all, Lewis only required it to function right on *true* challenges to its identity. I wish I could link to the text of the article (it’s just 4 pages), but the Canadian Journal of Philosophy seems not to have its issues from 1979 online.

(The reason I filed this under the category “set theory” is because of the last few lines of the first “Lucas against Mechanism”:

We do not know how Lucas verifies theoremhood in Lucas arithmetic, so we do not know how many of its theorems he can produce as true. He can certainly go beyond Peano arithmetic, and he is perfectly justified in claiming the right to do so. But he can go beyond Peano arithmetic and still be a machine, provided that some sort of limitations on his ability to verify theoremhood eventually leave him unable to recognize some theorem of Lucas arithmetic, and hence unwarranted in producing it as true.

This is I think exactly what set theorists are doing – trying to see just how far beyond PA (and in fact, beyond ZFC) they can go.)

Peter McB.(08:48:26) :The category theorist, Bill Lawvere, gave a categorial treatment of diagonalization arguments in a paper in 1968. This treatment generalizes both Cantor’s and Godel’s methods. Given such a formal representation of the argument, I see no reason why a machine could not be programmed to produce such arguments in appropriate circumstances. Penrose’s argument that AI is impossible because a machine could not generate a diagonal argument is thus easily rebutted.

Lawvere’s paper is:

F. W. Lawvere: “Diagonal arguments and cartesian closed categories.”

In: Category Theory, Homology Theory and their Applications, II (Battelle Institute Conference, Seattle, WA, 1968, Vol. Two), pages 134–145.

Springer, Berlin, 1969.

Peter McB.(07:25:41) :Kenny —

There is a nice 2003 paper by Noson Yanofsky of Brooklyn College on Lawvere’s arguments, available here:

http://arxiv.org/abs/math.LO/0305282