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 a 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 it for free. Note that there is a current version that gives a much better idea of the current state of the project.

Highlights


Get Theory of Computation

I have used this text in class twice. (A few 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 release is beta, 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 most current draft version. Get this version if you want to see what the text is about and don't care much about a few mostly cosmetic formatting nits. (The main formatting flaw is that some graphics fall off the bottom of a page. I only readjust the formatting once in a while, particularly as for the teaching versions.)


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. Please see the draft version for a reasonably up to date PDF.

Also, although the book has many exercises right now, it could use more in some sections. My practice is to 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. That takes a lot of time. Eventually I would like to make put of these exercises in a suitable online platform such as WeBWorK, Moodle, or Canvas.

After that, I will 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.)