What do you think?
Rate this book
Computability and Logic
Computability and Logic has become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as Godel’s incompleteness theorems, but also a large number of optional topics, from Turing’s theory of computability to Ramsey’s theorem. Including a selection of exercises, adjusted for this edition, at the end of each chapter, it offers a new and simpler treatment of the representability of recursive functions, a traditional stumbling block for students on the way to the Godel incompleteness theorems.
366 pages, Paperback
First published January 1, 1980
43 people are currently reading
782 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 14 of 14 reviews
January 5, 2008
BUY THE FIFTH EDITION!!!
This is the classic textbook for anyone who wants to study logic up to and beyond Godel. However, the 4th edition is plagued with serious typographic errors in the exercises. Several proofs are, in fact, impossible. John Burgess has a list of corrections on his website, but it is better just to buy the corrected fifth edition.
This is the classic textbook for anyone who wants to study logic up to and beyond Godel. However, the 4th edition is plagued with serious typographic errors in the exercises. Several proofs are, in fact, impossible. John Burgess has a list of corrections on his website, but it is better just to buy the corrected fifth edition.
September 7, 2015
Jus absolutely delightful. Assumming little background knowledge, it has been incredibly satisfying to be shown how various computational systems work, and then also to show that they're equivalent. Beautiful. Not finished yet.
January 4, 2021
Part I introduces the reader with the basics of computability theory. It contains discussions of Turing machines, Abacus machines, and recursive functions, and proves their equivalence. In the final chapter there is a light introduction to recursive and semi-recursive sets.
Part II skims through the basics of the syntax and semantics of first-order logic and then hastily goes on to relate logic and computability by giving two proofs of Church's theorem. The next chapters prove the compactness theorem (without appealing to Gödel's completeness theorem), the downward Löwenheim–Skolem theorem, and then introduce the reader to sequent calculus and demonstrate its soundness and completeness. The introduction to first-order logic is rushed which seems appropriate since the book is intended at students who have encountered the topic before, but the next chapters are really clear, except the introduction to sequent calculus which was totally undecipherable for me (although I had worked with Gentzen-style natural deductions and axiomatic proofs before) until I looked at the relevant chapter in David Bostock's Intermediate Logic. Then come the chapters set the stages for the limitative theorems. Chapter fifteen is on arithmetization, and chapter sixteen on the representability of recursive functions. In the seventeenth chapter the diagonalization lemma is proves, and thanks to the previous chapters, Tarski' indefinability theorem, the undecidability of arithmetic, Church's theorem, and Gödel's first incompleteness are proved in two pages. The upside is that these results show their systematic relation very clearly, but the problem is that the presented proof differs from Gödel's original proof in not providing the undecidable sentence. Fortunately this problem is resolved in a section on undecidable sentences, which along the Gödel and Rosser sentences presents the Gödel-Grelling, Gödel-Berry, and Gödel-Chaitin formulas. Then the book moves to prove the second imcompleteness via Löb's theorem. Similar to virtually any other book the provability conditions of PA are not proved.
Part III discusses many different topics which are not included in the standard logic curriculum but may be of interest to many readers. Unfortunately errors (mostly typos) are found in nearly every chapter in the third section and many of the chapters in this part are not that clear. Chapters 19 and 20 on normal forms, Skolem functions, Herbrand's theorem, Craig's interpolation lemma, Robinson's joint consistency theorem, and Beth's definability theorem is lucid and on par with the first two parts. Chapter 21 contrasts Church's theorem with the fact that monadic logic is decidable, and then proves that even the logic of a dyadic relation is undecidable. Chapter 22 is a shallow treatment of second-order logic which even doesn't include Henkin's semantics. Chapter 23 first contrasts Tarski's theorem with two positive results, and then goes on to prove Addison's theorem via forcing. Unfortunately the authors don't give enough clues to the motivations of the proof. The next chapter delves into the topic of arithmetic's and PA's nonstandard models and proves two strengthened versions of Tenenbaum's theorems. Of all the chapters in Part III this was the most fascinating one for me, and made me plan to read Kaye's book on the topic. The final two chapters discuss Ramsey's theorem and provability logic. The chapter on Ramsey's theorem proves the theorem in a rather unusual way including a very boring application of compactness theorem which along merely stating the Paris-Harrington theorem is the only relation of the chapter to logic. The final chapter on provability logic introduces propositional modal logic from scratch and goes rather hurriedly to prove some substantive results in the GL modal logic and discusses how theorems of modal logic can be "cashed out" as theorems about provability in PA.
Finally the book is really lucid, and a must-read for anyone interested in logic. The first two parts give a very good treatment of some main topics in the logic curriculum, and the third part, though uneven at places, gives hints to more advanced topics.
Part II skims through the basics of the syntax and semantics of first-order logic and then hastily goes on to relate logic and computability by giving two proofs of Church's theorem. The next chapters prove the compactness theorem (without appealing to Gödel's completeness theorem), the downward Löwenheim–Skolem theorem, and then introduce the reader to sequent calculus and demonstrate its soundness and completeness. The introduction to first-order logic is rushed which seems appropriate since the book is intended at students who have encountered the topic before, but the next chapters are really clear, except the introduction to sequent calculus which was totally undecipherable for me (although I had worked with Gentzen-style natural deductions and axiomatic proofs before) until I looked at the relevant chapter in David Bostock's Intermediate Logic. Then come the chapters set the stages for the limitative theorems. Chapter fifteen is on arithmetization, and chapter sixteen on the representability of recursive functions. In the seventeenth chapter the diagonalization lemma is proves, and thanks to the previous chapters, Tarski' indefinability theorem, the undecidability of arithmetic, Church's theorem, and Gödel's first incompleteness are proved in two pages. The upside is that these results show their systematic relation very clearly, but the problem is that the presented proof differs from Gödel's original proof in not providing the undecidable sentence. Fortunately this problem is resolved in a section on undecidable sentences, which along the Gödel and Rosser sentences presents the Gödel-Grelling, Gödel-Berry, and Gödel-Chaitin formulas. Then the book moves to prove the second imcompleteness via Löb's theorem. Similar to virtually any other book the provability conditions of PA are not proved.
Part III discusses many different topics which are not included in the standard logic curriculum but may be of interest to many readers. Unfortunately errors (mostly typos) are found in nearly every chapter in the third section and many of the chapters in this part are not that clear. Chapters 19 and 20 on normal forms, Skolem functions, Herbrand's theorem, Craig's interpolation lemma, Robinson's joint consistency theorem, and Beth's definability theorem is lucid and on par with the first two parts. Chapter 21 contrasts Church's theorem with the fact that monadic logic is decidable, and then proves that even the logic of a dyadic relation is undecidable. Chapter 22 is a shallow treatment of second-order logic which even doesn't include Henkin's semantics. Chapter 23 first contrasts Tarski's theorem with two positive results, and then goes on to prove Addison's theorem via forcing. Unfortunately the authors don't give enough clues to the motivations of the proof. The next chapter delves into the topic of arithmetic's and PA's nonstandard models and proves two strengthened versions of Tenenbaum's theorems. Of all the chapters in Part III this was the most fascinating one for me, and made me plan to read Kaye's book on the topic. The final two chapters discuss Ramsey's theorem and provability logic. The chapter on Ramsey's theorem proves the theorem in a rather unusual way including a very boring application of compactness theorem which along merely stating the Paris-Harrington theorem is the only relation of the chapter to logic. The final chapter on provability logic introduces propositional modal logic from scratch and goes rather hurriedly to prove some substantive results in the GL modal logic and discusses how theorems of modal logic can be "cashed out" as theorems about provability in PA.
Finally the book is really lucid, and a must-read for anyone interested in logic. The first two parts give a very good treatment of some main topics in the logic curriculum, and the third part, though uneven at places, gives hints to more advanced topics.
September 16, 2016
Written for an audience with little more background in Math than the absolute basics of Set Theory (probably reading the Enderton book on Set Theory is enough prep for this one, and that's a very light read), it casts a great many interesting theorems in Logic and Computability as so many instances of the non-enumerability of the reals. It's very interesting to see how much is equivalent to that one fact, but I also can't help but feel that some of the proofs could benefit from a different perspective. In any case, though, it's good for the novice and even a worthwhile quick read for a more advanced audience who hasn't seen this exact presentation before.
March 2, 2017
Ehh. Not the best written book. Some of the proofs could have been better formatted so that it was easier to read and understand. The sentences are long winded and aren't direct enough. Or maybe I'm just very bad at comprehending logic. Hm.
The turing machine chapters are decent. The FOL chapters could have done with some rework. Some of the proofs were blocks of text, and within them they would reference certain stages of the proof, but it wasn't specified which ones, therefore the reader had to guess what part A B C was and where it's subproof started.
The turing machine chapters are decent. The FOL chapters could have done with some rework. Some of the proofs were blocks of text, and within them they would reference certain stages of the proof, but it wasn't specified which ones, therefore the reader had to guess what part A B C was and where it's subproof started.
June 9, 2019
I read this to get a rough overview over questions of Turing computability. I liked how it‘s written and could follow the proofs okay (I have little background in maths). Caveat though: I quickly lost motivation if the proofs went over multiple pages and skipped them, which hindered my understanding in the later chapters.
April 3, 2023
A classic in the field. Very lucid and easy to follow presentation of first-order logic. At times, it becomes more unclear and highly technical, but on balance it is likely one of the most comprehensive and readable books on the subject. Builds from primitives to logic to formal systems to incompleteness, masterfully in ways that promote understanding and competency.
June 16, 2024
Although a scientific textbook, the approach is fresh and reader-friendly. All important proofs are sketched informally before getting deeper into hard math.
January 5, 2008
A vast improvement over the fourth edition. Still the best introduction to advanced logic and metatheory.
December 7, 2010
Godels incomputability problem. Logic III.
May 9, 2013
Brutal
June 22, 2013
Simple, yet complete, presentation of the underlying theories of Computability; beautifully explained.
November 24, 2014
You should probably pick up a book on how to effectively, and elegantly, write a proof before reading this.
Read
May 3, 2016My mind is full of knowledge.
Displaying 1 - 14 of 14 reviews