Introduction to the Theory of Computation

Citation

Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

Chapter Summary

The book is organised in three parts that follow the traditional sequence of the subject: automata and languages, computability theory, and complexity theory. A preliminary Chapter 0 comes first, and each chapter ends with exercises, problems and solutions. The author describes the book as a textbook for an upper-division undergraduate or introductory graduate course covering automata theory, computability theory and complexity theory.

Chapter 0: Introduction

The opening chapter collects the mathematical background used throughout, including sets and graphs, with numbered examples and problems. It is where the book's habit of stating definitions and theorems formally and proving them is first set out.

Part One, Chapters 1–2: Automata and Languages

Chapter 1, "Regular Languages", introduces the simplest models of computation and the languages they recognise. Chapter 2, "Context-Free Languages", moves to the next level of expressive power. The third edition added a new section here, on deterministic context-free grammars, which the publisher presents as a first-of-its-kind theoretical treatment connected to parsing and LR(k) grammars.

Part Two, Chapters 3–6: Computability Theory

Chapter 3, "The Church–Turing Thesis", introduces the Turing machine as the standard model of what an algorithm can do. Chapter 4, "Decidability", asks which problems can be solved by such machines at all. Chapter 5, "Reducibility", develops reductions as the main tool for showing that further problems are undecidable. Chapter 6, "Advanced Topics in Computability Theory", extends the part with further results beyond the core sequence.

Part Three, Chapters 7–10: Complexity Theory

Chapter 7, "Time Complexity", turns from what can be computed to what can be computed within a resource bound. Chapter 8, "Space Complexity", does the same for memory. Chapter 9, "Intractability", examines problems that are provably hard, and Chapter 10, "Advanced Topics in Complexity Theory", closes the book with further topics.

Key Concepts

Part One: Automata and languages

• Regular languages: the languages recognised by the simplest models of computation, the subject of Chapter 1.
• Context-free languages: the next class, the subject of Chapter 2, with deterministic context-free grammars added in the third edition.

Part Two: Computability

• Turing machines and the Church–Turing thesis: the formal model that stands for the intuitive notion of an algorithm.
• Decidability: whether a problem can be solved by an algorithm at all.
• Reducibility: transferring undecidability from one problem to another by a reduction.

Part Three: Complexity

• Time and space complexity: measuring the resources a computation needs, the subject of Chapters 7 and 8.
• Intractability: problems that are provably hard, the subject of Chapter 9.

Critical Analysis

Strengths

• Clarity. Cengage describes the book as keeping an approachable style with timely revisions, additional exercises and more memorable examples, while maintaining rigour and formalism.
• A single path through three subjects. The parts follow the order in which most courses teach the material: automata first, then computability, then complexity. Chapters 3–5 build decidability and reducibility in sequence on the Turing machine.
• Exercise support. Every chapter ends with exercises, problems and solutions; the third edition adds new exercises, problems and solutions, and the author maintains a public errata list for the edition.
• Parsing connection. The new section on deterministic context-free grammars links the theory to LR(k) parsing, which is useful for readers who meet grammars in compiler courses.
• Used by its author. Sipser teaches from the third edition in his own MIT course (see Common course assignments below), so the book's sequence can be followed alongside a complete course built around it.

Limitations

• Proof-based throughout. The publisher stresses mathematical treatments "including advanced theorems and proofs", so readers with little proof experience should expect to learn proof-writing alongside the material.
• Theory only. The book contains no programming-based material; readers who want to see computability through running programs will need another source.
• Advanced chapters are selective. Chapters 6 and 10 are collections of further topics, not a full development of any single one. Even the author's own MIT course, described below, assigns only selected sections from Chapters 6, 9 and 10.

Where It Fits in the Course

Sipser is the standard proof-oriented core text for the subject, and the author's MIT course builds its full semester around the third edition. Peter Linz and Susan Rodger's An Introduction to Formal Languages and Automata is a gentler introduction that favours explanation and worked examples over heavy formalism. John MacCormick's What Can Be Computed? grounds computability and complexity in short Python programs before the formal arguments, which makes it a good first book for readers who find the formal approach abstract. Dexter Kozen's Automata and Computability is organised as short lectures with full proofs and a large set of graded exercises. Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation is the classic alternative with a similar scope. Arora and Barak's Computational Complexity is a graduate-level book that continues where Chapters 7–10 stop.

How to Use This Book

The book suits upper-level undergraduates and beginning graduate students who have taken discrete mathematics and can read and write proofs. This guide refers to the third edition (Cengage, 2012, ISBN 9781133187790). Section numbers in course syllabi are tied to that edition, so check which edition you own before following a reading list.

A practical plan:

• Core: Chapter 0 for notation (skim if familiar), then Chapters 1–5 and 7 in order. These give a complete first course: regular and context-free languages, Turing machines, decidability and reductions, and time complexity.
• Next: Chapter 8 on space complexity and Chapter 9 on intractability.
• Optional: the final sections of Chapter 2 on deterministic context-free grammars if you are interested in parsing, and the "advanced topics" Chapters 6 and 10 for a longer or graduate-level course.
• Practice: attempt each exercise and problem before looking at the solutions, and write proofs out in full sentences; the book's own proofs are a model for this. Check the author's errata list for the edition you own.

A reader who finds Chapters 1–2 abstract can start with a gentler or program-based book and return to Sipser for Chapters 3–5, where computability is introduced. For self-study, keep a notebook of the main reductions and proof patterns from Chapters 4, 5 and 7. These patterns recur from chapter to chapter, and re-deriving them from memory is a quick test of understanding.

Common course assignments

The clearest recent model for a one-semester course is MIT OpenCourseWare's 18.404J Theory of Computation, Fall 2020, taught by Sipser and using the third edition (2012). Its readings page assigns:

• Automata and languages: Chapter 1 in full, and Chapter 2 except Section 2.4.
• Computability: Chapters 3, 4 and 5 in full, plus Section 6.1.
• Complexity: Chapters 7 and 8 in full, Sections 9.1 and 9.2, Section 10.2 (except the primality material), and Section 10.4 up to Theorem 10.33.

This lines up closely with the core-then-next plan above. The course covers Chapters 1–5, 7 and 8 essentially in full and dips selectively into the advanced chapters. The readings page also has a lecture-by-lecture table mapping each lecture to sections from 1.1 through 10.4. Self-study readers can use it as a pacing schedule, alongside the course's other OpenCourseWare materials.