Sign inSign in

Theory & Algos · Book

Introduction to the Theory of Computation

Michael Sipser

Sipser wrote the book for MIT's 18.404J and develops the theory of computation through theorems and proofs.

Michael SipserCourse text for 18.404JCengage Learning2012504 pagesnamed in 10 lectures

Watch the course it teaches · 18.404JFind a copy

Opens a bookshop outside Lectern.

Read alongside

Named in lectures

31:38

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

25:14

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.

1:32

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.

7 more moments

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

No reader has written about it yet.

Write the first review

Where next

16 connections