Computability theory (Q2891272)

This short text does an excellent job of covering those topics that should be included in an undergraduate introduction to computability theory. After a chapter efficiently introducing a minimal amount of mathematical logic and notation, the longest chapter of the book explores the concept of computable functions, using Turing machines as the primary (but not only) model. Subsequent chapters accessibly present other central topics in computability, for example: the recursion theorem, c.e.~sets, Turing reducibility, decision problems, incompleteness, priority arguments, and the arithmetical hierarchy. There are both appropriate exercises and enticing doorways to open topics and current research. The exposition is precise, but still conversational. I believe my students will enjoy reading this text.