Theory of Computation is a text for a first undergraduate course. It is Free. Use it as a main text, as a supplement, or for independent study.

Are you teaching with this text?

You and your students can get a paper version. (The hardcopy can differ in a number of small ways from the electronic version that you can download. There may be some typo corrections that have not yet made it to paper, and of course the animations in the PDF do not run on paper. Also, some illustrations are not in the paper version for licensing reasons, which changes pagination.)

You may find these materials useful.

  • Beamer slides I use these for classroom presentation. These cover the same material as the text, in the same order. They are made using the book's LaTeX source so they are sure to have the same wording, notation, etc.
  • The answers to exercises contains worked solutions to all exercises.
  • Videos I've made a sequence of video lectures. Like the text, they emphasize motivation and examples. Most are 20–25 minutes, with longer topics split in two. They are intended for people working through the material on their own, but others may also find them useful.
  • Machine simulation programs These are in Racket. They are organized by chapter. (Some are under development.)

Suggested additional readings

These books are available at most college or university libraries.

The Universal Computer: The Road from Leibniz to Turing, by Martin Davis (ISBN-13: 978-0393047851) is a wonderful historical overview of the development of the subject, written for a wide audience by one of the central people in that development.

Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas Hofstadter (ISBN-13: 978-0465026562) is a charmingly discursive exploration of many of the ideas of the course (it is also a Pulitzer Prize winner).