Theory & Algos · Book
Introduction to the Theory of Computation
Sipser wrote the book for MIT's 18.404J and develops the theory of computation through theorems and proofs.
Read alongside
Named in lectures
Course Overview and Formal Definition of Computation · Ryan O'Donnell · CMU 15-455
Sipser, used as the main textbook for the course, focusing on Part 3 (Complexity Theory).
Turing Machines · Ryan O'Donnell · CMU 15-455
Sipser textbook, cited for using a one-way infinite tape compared to the lecturer's two-way infinite tape model.
Simulations and Turing Machine Variants · Ryan O'Donnell · CMU 15-455
Sipser, cited for his official model of computation with a one-way infinite tape.
Concepts
Good fit if
Written by Michael Sipser for MIT 18.404J—universally admired for its crystal-clear proofs of undecidability, reducibility, and complexity classes.
About the book
The third edition adds a theoretical treatment of deterministic context-free languages, tied to parsing and LR(k) grammars. The proofs go on to undecidability, reducibility and complexity classes. The book is pitched at undergraduates taking a course in computational theory, and this edition adds practice material and new examples.
Author
Readers
Where next


Connections
16Its authors, the courses that use it and the lectures that cite it.
