Theory of Computation by Jim Hefferon, along with its companion answers to exercises, is a text for a one semester first undergraduate Computer Science theory course. It is Free. Use it as the main book, as a supplement, or for independent study.
Highlights
- Standard coverage Definition of computation with Turing machines, unsolvable problems starting with the Halting problem, languages and graphs, Finite State machines, and complexity including P vs NP. More detail is in the Table of Contents.
- Liberal development This book encourages students to engage with the material conceptually. For example, we start with the definition of a computable function using Turing machines and thus on the first page we are tackling the subject's most natural and compelling question: What can be done? We follow that with a careful discussion of Church's Thesis. The development also addresses other topics that can give trouble such as nondeterminism, fine points of Big O, and the status of the P=NP question. This engagement helps students build a robust mental framework to support the technical results. That is, this text is distinguished by an exposition prompting students to reflect on the ideas underlying the formalities and to make connections with their other work.
- Lively The presentation is stimulating without sacrificing precision. There are many illustrations (more than a figure per page) along with many links and notes encouraging students to dive deeper. A bonus of this readability is that it supports instructors who incorporate active learning methods, such as having students read material independently.
- Exercises Students learn the most while doing problems. Each section ends with many exercises — the book has more than eight hundred — ranging from straightforward to quite challenging. They include exercises that explicitly address common misconceptions. The answer book has fully-worked solutions to each one. (In the PDF, click on an exercise number to go to the answer and click on the answer number to go back to the exercise.)
- Extras There are beamer slides for classroom presentation, along with videos based on those slides. Also, chapters close with a number of short supplemental topics that are useful for a brief digression, for independent or assigned reading, or for honors or small group projects. There are also machine simulation programs, written in Racket.
- Prerequisites A standard course in Discrete Mathematics: propositional logic, predicates, proof methods including induction, number theory such as primes and factoring, and sets, functions, and relations. The book has reviews for the topics of strings, functions, and propositional logic. It also includes sections on grammars, graph theory, and Big O (this uses L'Hôpital's rule and so requires derivatives), which may be new for students in some majors but review for others.
- Free Everything is Freely available, including the LaTeX source.
Current version
The book is ready to be used, version 1.10. I have classroom tested the material a number of times. I greatly appreciate feedback, including bug reports.
The text works well in any PDF viewer. A few of the figures are animated or have opacity and to see these use a PDF viewer that supports those features, such as Adobe Reader. In particular, my browser's PDF built-in viewer does not show some figures that do appear in Atril or Adobe Reader.