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 introductory course required for a degree in Computer Science, or taken by students in related areas such as Mathematics. You can use it as a main text, or as a supplement, or for independent study.

It is free for download. This is a beta version. I am using it in class this semester for the second time.

Highlights


Get Theory of Computation

Here is the current version of the text. (A couple of the figures are animated. You can get along fine without seeing the animations but to run them you need a PDF reader that supports this; the only one I know of is Adobe Reader.)

This is a beta release, version 0.85. I apologize for deficiencies but the text is, as I say, in development. I greatly appreciate feedback, including bug reports; my email is at the top of the page.

Many, many corrections and improvements are in the draft version. However, this may have some formatting flaws such as graphics that fall off the bottom of a page. Making the formatting adjustments is a chore that I only get to once in a while but if you want a recent version and don't care about a few mostly cosmetic nits, then this is for you.


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 review subsection.


Plans

Since this is a beta version, development and corrections are an important part of the work. Also, although the book has many exercises right now, it could use more in some sections. I would like to make some of these available in a suitable online platform, such as WeBWorK, Moodle, or Canvas. I write answers to all exercises, in part because it goes a long way to ensuring the exercises are solvable and in part because I find it greatly improves the text body. That takes considerable time.

I will then 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 is more effective, pedagogically, with these folks 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. 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 enjoy hearing about the experience that folks have with the book and 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 then I'd be interested to see it. Of course I reserve the ability to choose whether to edit it, or include it. I gratefully acknowledge all the contributions that I use I can keep you anonymous if you prefer).

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