Computability and Logic

by George S. Boolos, John P. Burgess, Richard C. Jeffrey

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.

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

366 pages, Paperback

First published January 1, 1980

Reviews

[Lane Wilkinson]

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]

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]

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]

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]

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]

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]

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]

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

[Chris Rhodes]

Godels incomputability problem. Logic III.

[Frank]

Brutal

[Warunika Ranaweera]

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

[Correy]

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.