Computability and Logic

Rating:
Summary: Prefer the old edition
Review: I have used the old edition for a class in computability and logic where the students did not have much background in either. Having used the new edition this year, I find I greatly prefer the old one. The new one may be more rigorous, but it is much harder to read and understand for students without the background. The first part is not so bad, but the second half on logic gets too involved in the proofs and the students lose sight of the overall pupose and what these result really mean.

Rating:
Summary: Don?t bother if this is not required reading
Review: Don't bother if this is not required reading

As a Maths graduate, and one who still reads the subject for fun, I thought I could handle things mathematical until I came by this book. Admittedly, the subject of this book is not my area, so I may be talking out of turn.

So, my criticisms? The book is written in a rather stilted style. The words do not flow easily, but, worse, the mathematical ideas also assume a lot of the reader. A proof could be presented in a couple of simple lines, but when you dig further, it assumes some intermediate steps. Even simple concepts like operations with Turing machines are made obtuse. What a contrast, with Roger Penrose, who gives a lucid explanation in his "The Emperor's New Mind"!

The sections on Logic are equally obscure, and extremely boring in their presentation. I am sad to say that this is the FIRST Maths text that made me fall asleep. The authors could not have done better if they had ventured out to find a cure for insomnia.

Sorry!

Rating:
Summary: almost great
Review: Except for the scores of typos. Previous reviewers have observed this already; one has added that Burgess maintains an errata file on his website at Princeton. In fact he has two (for 1st and 2nd printings). But note that the errata file, at least for the 1st edition, is far from complete. I've noticed at least a dozen (potentially very confusing) typos that he has not yet catalogued. It's very frustrating to have to check the errata file (over 40 pages!) everytime one gets confused.

Two more points (1) the proof of compactness could have been better organized, and thereby made less tedious. (2) In general, there could stand to be more meta-level discussion about what's going on in the book. I find it's mostly trees, very little forest. (I'm not asking for _Godel, Escher, Bach_ here; I mean: where is this proof headed? Where did these satisfacton properties come from? etc)

On the positive side, the book is comprehensive, with very little handwaving, and the chapters are usually short and sweet. I prefer this text to Mendelson's. Enderton's is not bad.

Rating:
Summary: Great textbook, poor text
Review: I can hardly imagine a better introduction to the topics covered than this book. It discusses virtually everything the intermediate logic student could want: diagonalization, Turing machines, undeciability, indefinability, incompleteness, forcing, and on and on. Although the first few chapters are a bit awkward, the style is generally crystal clear and the examples and metaphors vivid. It's far and away the best read of any text on logic I've yet encountered.

As a mathematician, I was concerned about the books' emphasis on logic rather than mathematics (the text is aimed at philosophy students, too). But the introduction to foundations flows so easily and naturally that I could never complain. Anyone interested in the topic, regardless of their background, could hardly do better (or cheaper) for an introduction.

P.S. - I wanted to give this five stars, but, as other reviewers have pointed out, there are simply too many typos. C'mon, get an editor.

Rating:
Summary: Not much to add, but
Review: it should be noted that this book is not intended for the auto-didact. Like other good logic texts-Jeffrey's Formal Logic or Pollock's Technical Method's (out of print, but available in PDF on his website)-there is very little commentary in the brief chapters, so it is useful if you are already very familiar with the material or if you have a very worthy guide. An advantage of the short chapters is that material is broken down in finer increments; a disadvantage is that material is presented with spare guidance at times. I was also disappointed by the sparsity of examples. Like many logic and math students, I learn better from examining a few examples than I do from either lectures or text: give me three examples of something and I'll usually have it down. I would have liked to see more examples in this text. The exercises are ample and creative, which I appreciate, but often go so far beyond the text it's mind boggling. They often require extensive extrapolations from the text sometimes even proving theorems or lemmas not in the text just for use in the exercise. I should say that I'm a philosopher and not a mathematician (I suspect the other reviewers are primarily mathematicians), so my estimation of the difficulty will differ. I aced Symbolic Logic, Modal Logic, Deviant Logic, and Advanced Symbolic Logic and still had difficulty with some of this material, even though I had a prior acquaintance with Godel's proof. Note that the first reviewer, who thought it was a breeze, described himself this way "As a topologist who recently got interested in computational topology..." Good for him, but if you are not a professional mathematician this book will probably be quite challenging at times, even if you are otherwise good at mathematical logic. Note also that the second five-star review refers to the older edition-it has not necessarily improved with age. I firmly agree with the reviewer from Brooklyn that the proofs could have had more forecasting and with the reviewer from Raleigh that a solution set, say to the odds, would have been very useful, especially for the auto-didact, from whose perspective I am writing.

Rating:
Summary: Not much to add, but
Review: it should be noted that this book is not intended for the auto-didact. Like other good logic texts-Jeffrey's Formal Logic or Pollock's Technical Method's (out of print, but available in PDF on his website)-there is very little commentary in the brief chapters, so it is useful if you are already very familiar with the material or if you have a very worthy guide. An advantage of the short chapters is that material is broken down in finer increments; a disadvantage is that material is presented with spare guidance at times. I was also disappointed by the sparsity of examples. Like many logic and math students, I learn better from examining a few examples than I do from either lectures or text: give me three examples of something and I'll usually have it down. I would have liked to see more examples in this text. The exercises are ample and creative, which I appreciate, but often go so far beyond the text it's mind boggling. They often require extensive extrapolations from the text sometimes even proving theorems or lemmas not in the text just for use in the exercise. I should say that I'm a philosopher and not a mathematician (I suspect the other reviewers are primarily mathematicians), so my estimation of the difficulty will differ. I aced Symbolic Logic, Modal Logic, Deviant Logic, and Advanced Symbolic Logic and still had difficulty with some of this material, even though I had a prior acquaintance with Godel's proof. Note that the first reviewer, who thought it was a breeze, described himself this way "As a topologist who recently got interested in computational topology..." Good for him, but if you are not a professional mathematician this book will probably be quite challenging at times, even if you are otherwise good at mathematical logic. Note also that the second five-star review refers to the older edition-it has not necessarily improved with age. I firmly agree with the reviewer from Brooklyn that the proofs could have had more forecasting and with the reviewer from Raleigh that a solution set, say to the odds, would have been very useful, especially for the auto-didact, from whose perspective I am writing.

Rating:
Summary: Good Textbook, Bad Problem Sets
Review: The textbook itself was pretty well written. The major problem I had with it was that the problem sets are RIDDLED with mistakes. The errata on their website help, but it doesn't catch everything. I sincerely hope the next edition has more proof reading before going to press.

Rating:
Summary: Very lucid explanations
Review: This book is regarded as a 'classic' and rightly so. It assumes a minimal background, some familiarity with the propositional calculus. Even this can be dispensed with, if the reader is sufficiently motivated, as there is a well-written review of the first-order logic that one typically learns in an introductory formal logic course.

The book is highly readable. Each chapter begins with a short paragraph outlining the topics in the chapter, how they relate to each other, and how they connect with the topics in later and earlier chapters. These intros by themselves are valuable. The explanations though are what stand out. The authors are somehow able to take the reader's hand and guide him/her leisurely along with plentiful examples, but without getting bogged down in excessive prose. And they are somehow able to cover a substantive amount of material in a short space without seeming rushed or making the text too dense. It's nothing short of miraculous.

What made the book especially appealing to me is that it starts right out with Turing Machines. As a topologist who recently got interested in computational topology, I needed a book that would quickly impart a good, intuitive grasp of the basic notions of computability. I have more "mathematical maturity" than is needed to read an introductory book on computability, so I feel confident in saying that most of the standard texts on computability revel in excessive detail, like defining Turing Machines as a 6-tuple -- something that serves no purpose other than pedantry. This book is different. I particularly liked how the authors stress the intuitive notions underlying the definitions. For example, they lay special emphasis on the Church-Turing thesis, always asking the reader to consider how arguments can be simplified if it were true.

One should note that the emphasis of this book is more towards logic. While it starts with issues of computability, it moves into issues of provability, consistency, etc. The book covers the standards such as Goedel's famous incompleteness theorems in addition to some less standard topics at the end of the book. A small set of instructive exercises follows each chapter.

Rating:
Summary: almost great
Review: This is the standard text for those who have only had an introductory logic class and want to work up to (and past) Godel's incompleteness theorems. The third edition was already good, and John Burgess has extensively rewritten parts to make the arguments clearer and easier to follow.

It is true that there are a number of typos, but a list of corrections can be downloaded from John Burgess's web site at Princeton University.

Rating:
Summary: Absolutely rediculous
Review: WAY TOO MANY TYPOS!!!!!! There were so many typos, it made it extremely difficult to follow this book at times. As a first time student to mathematical logic, I found this to be just too much. People who are veterans with logic and logicians may easily spot typos, but for a first time student of the subject, I was confused as hell at some parts simply because there was a typo. I wasted hours trying to figure out some parts (such as the factorial function in chapter 6) when I finally found out that the reason why I couldn't figure it out was because of a typo. The Errata sheet on the internet IS 35 PAGES LONG!!!! I didn't pay money to correct a horde of typos! God that pisses me off.