Computability and Logic

by George S. Boolos, Richard C. Jeffrey

A text for a second course in logic for graduate and advanced undergraduate students. This third edition has been corrected and contains thoroughly revised versions of the chapters on Ramsey and provability, with new exercises provided for three other chapters. There are also two new chapters dealing with undecidable sentences and on the non-existence of non-standard recursive models of Z.

Genres: Logic, Philosophy, Mathematics, Computer Science, Science, Textbooks, Nonfiction

304 pages, Paperback

First published January 1, 1980

Reviews

[Lane Wilkinson · Rating 1 out of 5]

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.

[Ben Pace · Rating 5 out of 5]

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.

[Adam · Rating 5 out of 5]

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.

[Ilinalta · Rating 2 out of 5]

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.

[Max · Rating 4 out of 5]

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.

[Lucille Nguyen · Rating 5 out of 5]

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.

[Jason Kowalski · Rating 5 out of 5]

Although a scientific textbook, the approach is fresh and reader-friendly. All important proofs are sketched informally before getting deeper into hard math.

[Lane Wilkinson · Rating 5 out of 5]

A vast improvement over the fourth edition. Still the best introduction to advanced logic and metatheory.

[Chris Rhodes · Rating 4 out of 5]

Godels incomputability problem. Logic III.

[Frank · Rating 3 out of 5]

Brutal

[Warunika Ranaweera · Rating 5 out of 5]

Simple, yet complete, presentation of the underlying theories of Computability; beautifully explained.

[Correy · Rating 4 out of 5]

You should probably pick up a book on how to effectively, and elegantly, write a proof before reading this.

[Micah]

My mind is full of knowledge.