Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Second Edition

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0005.djvu
Preface......Page __sk_0011.djvu
Acknowledgments......Page __sk_0015.djvu
Dependency Graph......Page __sk_0017.djvu
1. Sets and n-tuples......Page __sk_0019.djvu
2. Functions......Page __sk_0021.djvu
3. Alphabets and Strings......Page __sk_0022.djvu
4. Predicates......Page __sk_0023.djvu
5. Quantifiers......Page __sk_0024.djvu
6. Proof by Contradiction......Page __sk_0026.djvu
7. Mathematical Induction......Page __sk_0027.djvu
Part 1 Computability......Page __sk_0033.djvu
1. A Programming Language......Page __sk_0035.djvu
2. Some Examples of Programs......Page __sk_0036.djvu
3. Syntax......Page __sk_0043.djvu
4. Computable Functions......Page __sk_0046.djvu
5. More about Macros......Page __sk_0050.djvu
1. Composition......Page __sk_0057.djvu
2. Recursion......Page __sk_0058.djvu
3. PRC Classes......Page __sk_0060.djvu
4. Some Primitive Recursive Functions......Page __sk_0062.djvu
5. Primitive Recursive Predicates......Page __sk_0067.djvu
6. Iterated Operations and Bounded Quantifiers......Page __sk_0070.djvu
7. Minimalization......Page __sk_0073.djvu
8. Pairing Functions and Gödel Numbers......Page __sk_0077.djvu
1. Coding Programs by Numbers......Page __sk_0083.djvu
2. The Halting Problem......Page __sk_0086.djvu
3. Universality......Page __sk_0088.djvu
4. Recursively Enumerable Sets......Page __sk_0096.djvu
5. The Parameter Theorem......Page __sk_0103.djvu
6. Diagonalization and Reducibility......Page __sk_0106.djvu
7. Rice\'s Theorem......Page __sk_0113.djvu
*8. The Recursion Theorem......Page __sk_0115.djvu
*9. A Computable Function That Is Not Primitive Recursive......Page __sk_0123.djvu
1. Numerical Representation of Strings......Page __sk_0131.djvu
2. A Programming Language for String Computations......Page __sk_0139.djvu
3. The Languages S and S_n......Page __sk_0144.djvu
4. Post-Turing Programs......Page __sk_0147.djvu
5. Simulation of S_n in T......Page __sk_0153.djvu
6. Simulation of T in S......Page __sk_0158.djvu
1. Internal States......Page __sk_0163.djvu
2. A Universal Turing Machine......Page __sk_0170.djvu
3. The Languages Accepted by Turing Machines......Page __sk_0171.djvu
4. The Halting Problem for Turing Machines......Page __sk_0175.djvu
5. Nondeterministic Turing Machines......Page __sk_0177.djvu
6. Variations on the Turing Machine Theme......Page __sk_0180.djvu
1. Semi-Thue Processes......Page __sk_0187.djvu
2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes......Page __sk_0189.djvu
3. Unsolvable Word Problems......Page __sk_0194.djvu
4. Post\'s Correspondence Problem......Page __sk_0199.djvu
5. Grammars......Page __sk_0204.djvu
6. Some Unsolvable Problems Concerning Grammars......Page __sk_0209.djvu
*7. Normal Processes......Page __sk_0210.djvu
1. Using Oracles......Page __sk_0215.djvu
2. Relativization of Universality......Page __sk_0219.djvu
3. Reducibility......Page __sk_0225.djvu
4. Sets r.e. Relative to an Oracle......Page __sk_0229.djvu
5. The Arithmetic Hierarchy......Page __sk_0233.djvu
6. Post\'s Theorem......Page __sk_0235.djvu
7. Classifying Some Unsolvable Problems......Page __sk_0242.djvu
8. Rice\'s Theorem Revisited......Page __sk_0248.djvu
9. Recursive Permutations......Page __sk_0249.djvu
Part 2 Grammars and Automata......Page __sk_0253.djvu
1. Finite Automata......Page __sk_0255.djvu
2. Nondeterministic Finite Automata......Page __sk_0260.djvu
3. Additional Examples......Page __sk_0265.djvu
4. Closure Properties......Page __sk_0267.djvu
5. Kleene\'s Theorem......Page __sk_0271.djvu
6. The Pumping Lemma and Its Applications......Page __sk_0278.djvu
7. The Myhill-Nerode Theorem......Page __sk_0281.djvu
1. Context-Free Grammars and Their Derivation Trees......Page __sk_0287.djvu
2. Regular Grammars......Page __sk_0298.djvu
3. Chomsky Normal Form......Page __sk_0303.djvu
4. Bar-Hillel\'s Pumping Lemma......Page __sk_0305.djvu
5. Closure Properties......Page __sk_0309.djvu
*6. Solvable and Unsolvable Problems......Page __sk_0315.djvu
7. Bracket Languages......Page __sk_0319.djvu
8. Pushdown Automata......Page __sk_0326.djvu
9. Compilers and Formal Languages......Page __sk_0341.djvu
1. The Chomsky Hierarchy......Page __sk_0345.djvu
2. Linear Bounded Automata......Page __sk_0348.djvu
3. Closure Properties......Page __sk_0355.djvu
Part 3 Logic......Page __sk_0363.djvu
1. Formulas and Assignments......Page __sk_0365.djvu
2. Tautological Inference......Page __sk_0370.djvu
3. Normal Forms......Page __sk_0371.djvu
4. The Davis-Putnam Rules......Page __sk_0378.djvu
5. Minimal Unsatisfiability and Subsumption......Page __sk_0384.djvu
6. Resolution......Page __sk_0385.djvu
7. The Compactness Theorem......Page __sk_0388.djvu
1. The Language of Predicate Logic......Page __sk_0393.djvu
2. Semantics......Page __sk_0395.djvu
3. Logical Consequence......Page __sk_0400.djvu
4. Herbrand\'s Theorem......Page __sk_0406.djvu
5. Unification......Page __sk_0417.djvu
6. Compactness and Countability......Page __sk_0422.djvu
*7. Gödel\'s Incompleteness Theorem......Page __sk_0425.djvu
*8. Unsolvability of the Satisfiability Problem in Predicate Logic......Page __sk_0428.djvu
Part 4 Complexity......Page __sk_0435.djvu
1. The Blum Axioms......Page __sk_0437.djvu
2. The Gap Theorem......Page __sk_0443.djvu
3. Preliminary Form of the Speedup Theorem......Page __sk_0446.djvu
4. The Speedup Theorem Concluded......Page __sk_0453.djvu
1. Rates of Growth......Page __sk_0457.djvu
2. P versus NP......Page __sk_0461.djvu
3. Cook\'s Theorem......Page __sk_0469.djvu
4. Other NP-Complete Problems......Page __sk_0475.djvu
Part 5 Semantics......Page __sk_0483.djvu
1. Programming Language Semantics......Page __sk_0485.djvu
2. Partial Orders......Page __sk_0490.djvu
3. Complete Partial Orders......Page __sk_0493.djvu
4. Continuous Functions......Page __sk_0504.djvu
5. Fixed Points......Page __sk_0512.djvu
1. Syntax......Page __sk_0523.djvu
2. Semantics of Terms......Page __sk_0529.djvu
3. Solutions to W-Programs......Page __sk_0538.djvu
4. Denotational Semantics of W-Programs......Page __sk_0548.djvu
5. Simple Data Structure Systems......Page __sk_0557.djvu
6. Infinitary Data Structure Systems......Page __sk_0562.djvu
1. Operational Semantics for Simple Data Structure Systems......Page __sk_0575.djvu
2. Computable Functions......Page __sk_0593.djvu
3. Operational Semantics for Infinitary Data Structure Systems......Page __sk_0602.djvu
Suggestions for Further Reading......Page __sk_0611.djvu
Notation Index......Page __sk_0613.djvu
Index......Page __sk_0617.djvu