I’m teaching an upper level logic course from the fourth edition of Computability and Logic, which as anyone who has used it knows has an impressive number of errors. These are almost all relatively trivial typing and typesetting errors, but the problem with a book this error-riddled is that when something happens that you can’t quite follow, there’s a temptation to blame the book rather than your tiny addled brain. This is almost always a mistake when working in this area, but sometimes it becomes irresistable.
For instance, on page 194 (of the first printing) there’s a definition of what it is for x to be the code number of a simple atomic sentence, where a simple atomic sentence is one that doesn’t contain identity or function symbols. The account given there is that x is the code number for a sequence such that:
- The first member of that sequence is the code number of an n-place predicate, where 2n+2 is the length of the sequence
- The second member of that sequence is 1 (the code number of ‘(’)
- The next n odd-numbered places in the sequence are filled by the code numbers for atomic terms, which under our current hypothesis are constants or variables
- The intermediate even-numbered places in the sequence are filled by the number 5 (the code number of ‘,’)
- The last member of the sequence is 3 (the code number of ‘)’)
Now when we reinstate function symbols, we’re just told that the definition of an atomic term has to change to allow for the possibility that, for example, (0,0),0) is an atomic sentence despite satisfying only two of the five above requirements.
I don’t think this is too hard a problem to patch, but given the level of detail that’s gone into for the function-free language, it’s surprising that this is not only elided, but suggested to be a non-problem.
Having said all that, I should say that there is a lot to like about the fourth edition of C&L, especially for those of us who want to teach a course primarily on the incompleteness theorems and their implications for the logic of provability, and don’t want to take a detour through Turing machines to get there. And the problem sets are a great addition. So I think Burgess did a great job with the book. But sometimes I’m left scratching my head trying to follow what’s going on, and I’m not sure it’s always my fault.
Posted by Brian Weatherson in Uncategorized