Theory of Computation, Making Connections

A Free text for the undergraduate Computer Science course

Jim Hefferon
Mathematics and Statistics Department
University of Vermont

Theory of Computation is a text for the first course in theory, required for an undergraduate degree in Computer Science or taken by students in related areas such as Mathematics. You can use it as a main text, as a supplement, or for independent study.

Download the current version for free.

Please note: the canonical home page for this material is hefferon.net/computation. That site has the current descriptions of the materials and ancillaries, as well as the best contact information. It is also mobile-friendly. If you make links, please use that URL.

Highlights

• Standard coverage Definition of computation, unsolvable problems, Languages, Automata, Nondeterminism, and Complexity including the P=NP question. (See this comparison with the ACM recommendations.)
• Free The book is available for download, including its source.
• Development While covering the needed topics, this text gives students an overview of the subject, including an understanding of its successes and of its challenges. An example is that we don't start with finite state machines; rather, we ask what can be computed and then follow the natural development to the definition of Turing machines. This forgos some slickness but it is a good trade because it helps students build the right mental framework, and so make better sense of what we cover. There are many other examples of helping students internalize the concepts.
• Lively The development is precise but the writing is stimulating. There are many illustrations — more than a figure per page — as well as many links and notes for further reading. The exposition encourages students to make connections with other work and to reflect on the ideas behind the formal statements.
• Exercise sets Students learn the most when doing the problems and so sections end with many exercises. Overall, there are more than eight hundred of them, ranging from routine to quite challenging. The answer book contins worked solutions to all, including proofs.
• Topics Chapters finish with a number of short supplemental topics. These are valuable for independent or assigned reading, or for honors or small group work.
• Prerequisite The text assumes the standard course in Discrete Mathematics: propositional logic and truth tables, predicates, proof methods including induction, graphs, basic number theory such as primes, factoring, and modular arithmetic, and sets, functions, and relations. Where some students may have a gap, such as with graphs and Big O, the book has a review. (Big O uses a bit of Calculus.)

Get Theory of Computation

Here is the book, as well as the answers to exercises. If you save these files in the same directory then clicking on the question number takes you to its answer, and clicking on the answer number takes you back to the question.

A few of the figures are animated. You can get along fine without the animations, but to run them you need a PDF reader that supports this, such as Adobe Reader.

Source code

If you are into LaTeX then you may be interested in the source repository. This is useful for instructors who like the book but want to tweak.

License

This text is Free, available under the Creative Commons Attribution-ShareAlike 4.0 International License.

I have done my best to incorporate only materials whose license allows me to share them. If I have made a mistake then I apologize; please contact me so that I can fix it.

For bookstores: thank you for being concerned about my rights. I give instructors permission to make copies of this material, either electronic or paper, and give or sell those to students.

For instructors who want to modify the text. Please, feel free. But as a favor I ask that you include a statement about your modifications. That way people making reports know who to write. Putting something like this on the front page would be great: \fbox{\parbox{0.75\textwidth}{The material in the appendix on induction has been added by Professor Jones of UBU. For any reports about this material contact \url{sjones@example.com}.}}

Can You Help?

I greatly appreciate feedback, including bug reports. I am glad to hear from both teachers and students. My best contact information is on hefferon.net.

Although the book has many exercises, if you can share some that would be great. I also welcome exams or problem sets. (If you could contribute your TeX or LaTeX source that'd be great because then instructors can cut and paste.) And, if you have something larger that you are able to share, such as an end-of-chapter Topic, then I'd be most interested to see it. Of course I reserve the ability to include it, edited or not. I gratefully acknowledge all the contributions that I use, or I can keep you anonymous.

I would also welcome contrbutions related to emerging electronic tools. For instance, if you have sets of questions that are suitable for LMS's and that you could share with other users of this book then write me and we can see about making them available. The same holds for WeBWorK problem sets.

My contact information is on hefferon.net.

Related work

I have two other books that you may like. These are also Freely available. My Linear Algebra text has been widely used for many years, and comes with complete answers to all exercises, Beamer slides for classroom use, and a lab manual. My Introduction to Proofs text is for a proofs course taught using the Inquiry-Based method (sometimes called the Discovery Method or the Moore method).

You may also like my Cheat sheet for LaTeX math, aimed at undergraduates but useful for anyone.

Site Information

This site Joshua is located in the Mathematics and Statistics Department of the University of Vermont.

Joshua runs under Linux

Open Source software is a great idea. This project would not have gotten done without it.

(Credit for the logo to Matt Ericson.)