Book Review: Computability and Logic
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
- Enumerability
- Diagonalization
- Turing Computability
- Uncomputability
- Abacus Computability
- Recursive Functions
- Recursive Sets and Relations
- Equivalent Definitions of Computability
- A Précis of First-Order Logic: Syntax
- A Précis of First-Order Logic: Semantics
- The Undecidability of First-Order Logic
- Models
- The Existence of Models
- Proofs and Completeness
- Arithmetization
- Representability of Recursive Functions
- Indefinability, Undecidability, and Incompleteness
- The Unprovability of Consistency
- Normal Forms
- The Craig Interpolation Theorem
- Monadic and Dyadic Logic
- Second-Order Logic
- Arithmetical Decidability
- Decidability of Arithmetic without Multiplication
- Nonstandard Models
- Ramsey's Theorem
- Modal Logic and Provability
Subscribe to RSS Feed
= f037147d6e6c911a85753b9abdedda8d)