This is the website for the book Theory of Computing: An Open Introduction by Taylor J. Smith. The book is currently in its α pre-publication edition (September 2024).
- Download the book: it’s available for free, forever!
- Errata file
- Source files
About the Book
This book is suitable for courses on the theory of computing at both the undergraduate and graduate levels, and for self-study. Topics are introduced in a logical order: we begin with the simple finite automaton and progressively introduce stronger models of computation, up to the Turing machine. We then shift from the models themselves to what the models can compute, which opens up a discussion on computability and decidability. This leads us to a journey through complexity theory. The remainder of the book focuses on a selection of special topics.
So far, the α pre-publication edition of the book only includes undergraduate-level material; future editions will include the chapters listed in italic text (and more!)
- Regular Languages
- Context-Free Languages
- Decidable and Semidecidable Languages
- Decision Problems
- Proving Undecidability
- Foundations of Complexity
- Time Complexity
- Space Complexity
- Hardness, Completeness, and Complements
- Probabilistic Computation
- Provers, Verifiers, and Interactivity
The β pre-publication edition, including Chapters 6, 7, 8, and 9, is slated for release by September 2025 by the end of 2025 Real Soon Now.
Repositories
In addition to this website, you can find Theory of Computing: An Open Introduction in the following open educational resource repositories.
Licensing and Attribution
This book is published under a Creative Commons BY-SA 4.0 license. You are free to use and adapt the material in this book under the conditions that you provide an attribution to the source material and that you distribute any adapted material under the same Creative Commons BY-SA 4.0 license terms.
If you use or adapt the material from this book, please include the following attribution:
Taylor J. Smith. Theory of Computing: An Open Introduction. Self-published open educational resource, α pre-publication edition, 2024. taylorjsmith.xyz/tocopen/.
The attribution is also available as a BibTeX entry.
Contact the Author
I always welcome comments from readers, whether you found an error in the book, or you have a suggestion for something you would like to see in a future edition, or you just want to send me a nice note. Also, if you are an educator who has adopted the book in your course, please get in touch to let me know!
You can reach me via email at tjsmith [at] stfx [dot] ca.