PNG image: cover of Theory of Computation

Theory of Computation, Making Connections

A Free text for the undergraduate Computer Science course

Jim Hefferon
Mathematics and Statistics Department,
Saint Michael's College

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 permanent home page for this material is now hefferon.net. That site contains a complete list and the most current descriptions of the materials and ancillaries, as well as the best contact information. It is also mobile-friendly. The links here are still the most current ones, though.

Highlights


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. The only one that I know of is Adobe Reader.


Source code

If you are into LaTeX then you may be interested in the source repository. This is useful for folks who like the book but want to make small adjustments, such as adding a topic subsection.


License

This text is Free, available under the Creative Commons License 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 cover 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?

Development and corrections are an important part of the current work. I greatly appreciate feedback, including bug reports I am glad to hear from both teachers and students. I find suggestions helpful, especially bug reports. My best contact information is on the book's home page.

Although the book has many exercises, if you can share some that would be great. Particularly welcome are easy exercises. (I write answers to all exercises because it greatly improves the development.) 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 the emerging electronic tools. For instance, if you have sets of questions that are suitable for Moodle quizzes 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 email is at the top of this page.


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.


Picture of Joshua L. Chamberlin

Site Information

This site Joshua is located in the Mathematics and Statistics Department of Saint Michael's College in Colchester, Vermont USA.

Joshua runs under Linux

Powered by Linux logo

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

(Credit for the logo to Matt Ericson.)