Computability Theory

Preface

This book is intended to serve as a textbook for a one-term course on computability

theory (i.e., recursion theory), for upper-division mathematics and computer science

students. And the book is focused on this one topic, to the exclusion of such computer-

science topics as automata theory, context-free languages, and the like. This makes

it possible to get fairly quickly to core results in computability theory, such as the

unsolvability of the halting problem.

The only prerequisite for reading this book is a willingness to tolerate a certain

level of abstraction and rigor. The goal here is to prove theorems, not to calculate

numbers or write computer programs. The book uses standard mathematical jargon;

there is an appendix on “Mathspeak” to ...