Book Review: Computability and Logic

23 So8res 21 November 2013 01:52PM

I'm reviewing the books on the MIRI course list. After putting down Model Theory partway through I picked up a book on logic. Computability and Logic, specifically.

Computability and Logic

This book is not on the MIRI course list. It was recommended to me by Luke along with a number of other books as a potential way to learn provability logic.

Computability and Logic is a wonderful book. It's well written. It's formal, but pulls off a conversational tone. It demonstrates many difficult concepts with ease. It even feels nice — it's got thick pages, large text, and a number of useful diagrams.

That said, I didn't find it very useful to me personally.

This book is a wonderful introduction to computability, incompleteness, unsatisfiability, and related concepts. It masterfully motivates the connection between computability and logic (a subject near and dear to my heart). It could be an invaluable resource for anyone in computer science looking to branch out into logic. It starts with the basic concept of enumeration and takes you all the way through Löb's theorem: quite an impressive feat, for one textbook.

For me, though, it was on the easy side. I already knew all the computability stuff quite well, and skimmed over much of it. The logic sections were a good refresher, though they were somewhat rudimentary by comparison to Model Theory. (Actually, this book would have been a great precursor to Model Theory: It spent quite a bit of time motivating and fleshing out concepts that Model Theory dumps on your head.)

Still, while this book was not exactly what I needed, I highly recommend it for other purposes. Its contents are summarized below.

Contents

  1. Enumerability
  2. Diagonalization
  3. Turing Computability
  4. Uncomputability
  5. Abacus Computability
  6. Recursive Functions
  7. Recursive Sets and Relations
  8. Equivalent Definitions of Computability
  9. A Précis of First-Order Logic: Syntax
  10. A Précis of First-Order Logic: Semantics
  11. The Undecidability of First-Order Logic
  12. Models
  13. The Existence of Models
  14. Proofs and Completeness
  15. Arithmetization
  16. Representability of Recursive Functions
  17. Indefinability, Undecidability, and Incompleteness
  18. The Unprovability of Consistency
  19. Normal Forms
  20. The Craig Interpolation Theorem
  21. Monadic and Dyadic Logic
  22. Second-Order Logic
  23. Arithmetical Decidability
  24. Decidability of Arithmetic without Multiplication
  25. Nonstandard Models
  26. Ramsey's Theorem
  27. Modal Logic and Provability
continue reading »