Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Preface - Pg. xi

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 explain some of this jargon. The basic material is covered in Chapters 1­4. After reading those chapters, Chapters 5, 6, and 7, which are largely independent of each other, can be read in any order. Chapter 1 is an informal introduction to the concepts of computability theory. That is, instead of an emphasis on precise definitions and rigorous proofs, the goal is to convey an intuitive understanding of the basic concepts. The precision and rigor will