Computability and Decidability
The Turing Machine Halting Problem
Reducing One Undecidable Problem to Another
12.2 Undecidable Problems for Recursively Enumerable Languages
12.3 The Post Correspondence Problem
12.4 Undecidable Problems for Context-Free Languages
12.5 A Question of Efficiency
13 Other Models of Computation
13.1 Recursive Functions
Primitive Recursive Functions
Ackermann's Function
μ Recursive Functions
13.2 Post Systems
13.3 Rewriting Systems
Matrix Grammars
Markov Algorithms
L-Systems
14 An Overview of Computational Complexity
14.1 Efficiency of Computation
14.2 Turing Machine Models and Complexity
14.3 Language Families and Complexity Classes
14.4 The Complexity Classes P and NP
14.5 Some NP Problems
14.6 Polynomial-Time Reduction
14.7 NP-Completeness and an Open Question
Appendix A Finite-State Transducers
A.1 A General Framework
A.2 Mealy Machines
A.3 Moore Machines