Computability, Complexity, and Languages

PrefaceAcknowledgmentsDependency Graph Chapter 1 Preliminaries 1. Sets and n-Tuples 2. Functions 3. Alphabets and Strings 4. Predicates 5. Quantifiers 6. Proof by Contradiction 7. Mathematical InductionPart 1 Computability Chapter 2 Programs and Computable Functions 1. A Programming Language 2. Some Examples of Programs 3. Syntax 4. Computable Functions 5. More About Macros Chapter 3 Primitive Recursive Functions 1. Composition 2. Recursion 3. PRC Classes 4. Some Primitive Recursive Functions 5. Primitive Recursive Predicates 6. Iterated Operations and Bounded Quantifiers 7. Minimalization 8. Pairing Functions and Gödel Numbers Chapter 4 A Universal Program 1. Coding Programs by Numbers 2. The Halting Problem 3. Universality 4. Recursively Enumerable Sets 5. The Parameter Theorem 6. The Recursion Theorem 7. Rice's Theorem 67 Chapter 5 Calculations on Strings 1. Numerical Representation of Strings 2. A Programming Language for String Computations 3. The Languages l and ln 4. Post-Turing Programs 5. Simulation of l in T 6. Simulation of T in l Chapter 6 Turing Machines 1. Internal States 2. A Universal Turing Machine 3. The Languages Accepted by Turing Machines 4. The Halting Problem for Turing Machines 5. Nondeterministic Turing Machines 6. Variations on the Turing Machine Theme Chapter 7 Processes and Grammars 1. Semi-Thue Processes 2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes 3. Unsolvable Word Problems 4. Post's Correspondence Problem 5. Grammars 6. Some Unsolvable Problems Concerning Grammars 7. Recursion and Minimalization 8. Normal Processes 9. A Non-R.E. SetPart 2 Grammars and Automata Chapter 8 Regular Languages 1. Finite Automata 2. Nondeterministic Finite Automata 3. Additional Examples 4. Closure Properties 5. Kleene's Theorem 6. The Pumping Lemma and Its Applications 7. The Myhill-Nerode Theorem Chapter 9 Context-Free Languages 1. Context-Free Grammars and Their Derivation Trees 2. Regular Grammars 3. Chomsky Normal Form 4. Bar-Hillers Pumping Lemma 5. Closure Properties 6. Solvable and Unsolvable Problems 7. Bracket Languages 8. Pushdown Automata 9. Compilers and Formal Languages Chapter 10 Context-Sensitive Languages 1. The Chomsky Hierarchy 2. Linear Bounded Automata 3. Closure PropertiesPart 3 Logic Chapter 11 Propositional Calculus 1. Formulas and Assignments 2. Tautological Inference 3. Normal Forms 4. The Davis-Putnam Rules 5. Minimal Unsatisfiability and Subsumption 6. Resolution 7. The Compactness Theorem Chapter 12 Quantification Theory 1. The Language of Predicate Logic 2. Semantics 3. Logical Consequence 4. Herbrand's Theorem 5. Unification 6. Compactness and Countability 7. Gödel's Incompleteness Theorem 8. Unsolvability of the Satisfiability Problem in Predicate LogicPart 4 Complexity Chapter 13 Loop Programs 1. The Language L and Primitive Recursive Functions 2. Running Time 3. ln as a Hierarchy 4. A Converse to the Bounding Theorem 5. Doing without Branch Instructions Chapter 14 Abstract Complexity 1. The Blum Axioms 2. The Gap Theorem 3. Preliminary Form of the Speedup Theorem 4.