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
jhefferon at smcvt.edu

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.

Highlights


Get Theory of Computation

Here is the current book draft, as well as a draft of the answers to exercises. This book is now at version 0.92. (The compilation date is inside the front cover.) I greatly appreciate feedback, including bug reports; my email is at the top of the page.

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.


Plans

Development and corrections are an important part of the current work.

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, as I see what students need to know in order to do the exercises. When I have a suitable document I will post them. Eventually I would like to also put them in a platform such as WeBWorK, Moodle, or Canvas.)

After the answers to all exercises I will next develop a set of Jupyter notebooks so that students work through the presented concepts in code. For instance, working with code to enumerate Turing machines has more effect, pedagogically, than an abstract approach.


License

This text is Free. Use it under either the GNU Free Documentation License or the Creative Commons License Creative Commons Attribution-ShareAlike 2.5 License, at your discretion.

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 at the email at the top of this page.

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}.}} And if you want to share back your changes, please contact me.


Can You Help?

I am glad to hear from both teachers and students. I find suggestions helpful, especially bug reports. I save these and periodically revise.

If you have something larger that you are able to share back, 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).

In particular, I would welcome exams or problem sets. If you could contribute your TeX or LaTeX source that'd be great because then instructors could cut and paste.

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.)