What Can Be Computed? A Practical Guide to the Theory of Computation

Citation

MacCormick, J. (2018). What Can Be Computed? A Practical Guide to the Theory of Computation. Princeton University Press.

Chapter Summary

The book has eighteen chapters: an introductory overview, Part I on computability theory (Chapters 2–9), Part II on computational complexity theory (Chapters 10–14), Part III on origins and applications (Chapters 15–17) and a short conclusion. A preface for instructors discusses which kind of theory course the book serves, what is in and out, and possible courses built on it. The publisher states that the book gives equal emphasis to computability and complexity, uses Python programs in the text (with Java alternatives online), and states and proves standard theorems with full rigour; lecture slides and the Python programs are on the companion site. Chapters end with exercises.

Chapter 1: Introduction: What Can and Cannot Be Computed?

Sorts problems into tractable, intractable and uncomputable, gives a more detailed overview of the book, and sets out its prerequisites, goals and reasons for studying the theory of computation.

Chapter 2: What is a Computer Program?

Fixes the model used throughout Part I: "SISO" Python programs that take a single string in and return a single string out. It covers the Python needed, problematic programs, a formal definition of a Python program, decision programs and equivalent programs, and how real-world programs relate to this model.

Chapter 3: Some Impossible Python Programs

Uses proof by contradiction on programs that analyse other programs (yesOnString.py, yesOnSelf.py, notYesOnSelf.py) to show that certain programs cannot exist, and concludes that perfect bug-finding programs are impossible even though useful bug finders are not.

Chapter 4: What is a Computational Problem?

Introduces graphs, alphabets, strings and languages, defines computational problems and their categories, and gives the formal meaning of solving a problem and of recognizing and deciding a language.

Chapter 5: Turing Machines: the Simplest Computers

Defines Turing machines, builds some nontrivial ones, and moves from single-tape to multi-tape machines and then to Python programs, simulating Turing machines in Python in the other direction. It closes by noting that classical computers can simulate quantum computers and that all known computers are Turing equivalent.

Chapter 6: Universal Computer Programs: Programs That Can Do Anything

Presents universal Python programs and universal Turing machines, universal computation in the real world, programs that alter other programs, and problems that are undecidable but recognizable.

Chapter 7: Reductions: How to Prove a Problem is Hard

Introduces reductions for easiness and for hardness, the formal definition and properties of Turing reductions, and a long series of uncomputable problems, including ones not about programs, with a summary of proof techniques for uncomputability.

Chapter 8: Nondeterminism: Magic or Reality?

Defines nondeterministic Python programs and computation trees, shows that nondeterminism does not change what is computable, gives nondeterministic Turing machines formally, and discusses unrecognizable problems and why nondeterminism is worth studying.

Chapter 9: Finite Automata: Computing With Limited Resources

Covers deterministic and nondeterministic finite automata and their equivalence, regular expressions, nonregular languages, and combinations of regular languages.

Chapter 10: Complexity Theory: When Efficiency Does Matter

Introduces asymptotic running time and big-O notation, how to determine the running time of a program, why the computational model matters for complexity, and complexity classes.

Chapter 11: Poly and Expo: the Two Most Fundamental Complexity Classes

Defines the classes Poly and Expo, shows that they do not depend on the computational model, exhibits HALTEX as a problem in Expo but not in Poly, and discusses unreasonable input encodings.

Chapter 12: PolyCheck and NPoly: Hard Problems That Are Easy to Verify

Defines polytime verifiers and the class PolyCheck, defines NPoly through nondeterminism, proves the two identical, and argues that nondeterminism does seem to change what is computable efficiently.

Chapter 13: Polynomial-time Mapping Reductions: Proving X is as Easy as Y

Defines polytime mapping reductions, illustrates them with Hamilton-cycle problems, and connects CIRCUITSAT, SAT and 3-SAT through reductions.

Chapter 14: NP-Completeness: Most Hard Problems Are Equally Hard

Treats P versus NP, NP-completeness and NP-hardness, the consequences of P = NP, CIRCUITSAT as a hardest NP problem (the Cook–Levin theorem), the spread of NP-completeness and proof techniques for it.

Chapters 15–17: The Original Turing Machine; You Can't Prove Everything That's True; Karp's 21 Problems

Chapter 15 reads Turing's 1936 definition of a computing machine and discusses the Church–Turing thesis. Chapter 16 connects undecidability to mechanical proof and Gödel's incompleteness of arithmetic. Chapter 17 works through Karp's paper on twenty-one NP-complete problems and the reductions between them.

Chapter 18: Conclusion: What Will Be Computed?

A brief review of the big ideas about what can be computed.

Key Concepts

Chapters 1–4: Programs and Problems

• Tractable, intractable and uncomputable problems: the three categories that organise the book.
• SISO Python program: a program that maps one input string to one output string, the book's main model of computation.
• Recognizing versus deciding: accepting the strings in a language versus always halting with the correct yes or no answer.

Chapters 5–9: Machines, Universality and Reductions

• Turing equivalence: the result that Turing machines, Python programs and all known computers compute the same things.
• Universal program: a program that can run any other program given as input.
• Turing reduction: proving a problem uncomputable by showing that solving it would solve a known uncomputable problem.
• Nondeterminism: computation that branches into a tree of possibilities; it does not enlarge what is computable.
• Finite automaton and regular expression: models of computation with limited resources.

Chapters 10–14: Complexity

• Poly and Expo: the problems solvable in polynomial and in exponential time; the book's names for these classes before it turns to the standard P and NP.
• Verifier and PolyCheck: a program that checks a proposed solution quickly, and the class of problems with such checkers, shown equal to NPoly.
• Polytime mapping reduction: an efficient transformation of one problem into another.
• NP-completeness and the Cook–Levin theorem: the hardest problems in NP, with CIRCUITSAT as the first example.

Chapters 15–18: Origins and Applications

• Church–Turing thesis: the claim that machines can compute whatever humans can compute by following rules.
• Incompleteness: the consequence of undecidability that some true statements of arithmetic cannot be proved.

Critical Analysis

Strengths

• Real programs as the entry point. The publisher's description, the chapter titles and The Ubyssey's review (Angela Tian, August 2018) all point to the same design: impossibility, universality and reductions are first argued with Python programs that readers can run, before the standard Turing-machine formulations.
• Balanced coverage. Part I and Part II give roughly equal space to computability and complexity, and the complexity part builds slowly through Poly and Expo, verifiers and reductions before NP-completeness.
• Context beyond the syllabus. Part III reads Turing's original paper, links undecidability to Gödel's incompleteness theorem and works through Karp's twenty-one problems.
• Support material. Lecture slides and the programs are available on the companion site, and the Ubyssey review notes exercises at the end of each chapter and a bibliography that explains each source.

Limitations

• Light on formal languages. Finite automata and regular expressions take one chapter; context-free grammars, pushdown automata and the Chomsky hierarchy are not among the chapter topics. Courses that examine those need another text.
• Python in the foreground. Readers need to be comfortable reading Python; the Ubyssey review notes that programming experience is needed for the Python examples.
• Non-standard names. The book works with its own classes Poly, Expo, PolyCheck and NPoly before connecting them to P and NP, so students will need to map these names to the standard notation used in other books and in exams.
• Complexity stops at NP-completeness. Chapter titles show no treatment of space complexity or of later topics such as randomness or approximation.

Where It Fits in the Course

In the theory-of-computation course this is the most program-centred introduction. Linz and Rodger's An Introduction to Formal Languages and Automata, the other introductory text, devotes most of its length to automata, grammars and pushdown automata and ends with a parsing part; MacCormick spends that space on computability and complexity. Students in a course built around formal languages should use Linz and Rodger as the main text and MacCormick for the computability and NP-completeness material; in a course built around "what can computers do?", the reverse.

Sipser's Introduction to the Theory of Computation, Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation and Kozen's Automata and Computability treat the same theorems in the standard Turing-machine notation with more formal language theory; MacCormick works well as an intuitive first pass before them. Arora and Barak's Computational Complexity is a graduate text that takes complexity far beyond Chapter 14.

How to Use This Book

The publisher describes the book as written for undergraduates meeting the subject for the first time, with minimal prerequisites, and suitable for self-study. In practice, an introductory programming course with some Python and some exposure to proof by contradiction will make the early chapters run smoothly.

• Core: Chapter 1, then Part I in order (Chapters 2–8) and Part II in order (Chapters 10–14). The two parts build on each other, especially nondeterminism (Chapter 8) for NPoly (Chapter 12).
• Chapter 9: essential if the course examines finite automata; otherwise it can be read lightly.
• Part III: optional enrichment; Chapter 16 suits students interested in logic and mathematics, Chapter 17 those who want more NP-completeness practice.

Download the programs from the companion site and run them as you read, especially in Chapters 3, 6 and 7, where the impossibility arguments are built from programs that analyse other programs. Try modifying a program before reading the proof that it cannot exist. As you meet Poly, Expo, PolyCheck and NPoly, write down the standard names alongside them so that the move to other textbooks is easy.