Computability, Complexity, and Languages, Second Edition

Preface Acknowledgments Dependency Graph 1 Preliminaries 1. Sets and n-tuples 2. Functions 3. Alphabets and Strings 4. Predicates 5. Quantifiers 6. Proof by Contradiction 7. Mathematical Induction Part 1 Cmnputability 2 Programs and Computable Functions 1. A Programming Language 2. Some Examples of Programs 3. Syntax - 4. Computable Functions 5. More about Macros 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 Gijdel Numbers 4 A Universal Program 1. Coding Programs by Numbers - -- 2. The Halting Problem 3. Universality 4. Recursively Enumerable Sets 5. The Parameter Theorem 6. Diagonalization and Reducibility -_’ 7. Rice’ s Theorem *8. The Recursion Theorem *9. A Computable Function That Is Not Primitive Recursive 5 Calculations on Strings 1. Numerical Representation of Strings 2. A Programming Language for String Computations 3. The Languages Y and Yn 4. Post-Turing Programs 5. Simulation of-F”, in 9 6. Simulation of Yin Y 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 7 Processes and Grammars 1. Semi-Thue Processes 2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes 3. 4. 5. 6. *7. Unsolvable Word Problems Post’ s Correspondence Problem Grammars Some Unsolvable Problems Concerning Grammars Normal Processes 8 Classifying Unsolvable Problems 1. Using Oracles 2. Relativization of Universality 3. Reducibility 4. Sets r.e. Relative to an Oracle 5. The Arithmetic Hierarchy 6. Post’ s Theorem 7. Classifying Some Unsolvable Problems 8. Rice’ s Theorem Revisited 9. Recursive Permutations Part 2 Grammars and Automata 9 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 10 Context-Free Languages 1. Context-Free Grammars and Their Derivation Trees 2. Regular Grammars 3. Chomsky Normal Form 4. Bar-Hillel’ s Pumping Lemma 5. Closure Properties *6. Solvable and Unsolvable Problems 7. Bracket Languages 8. Pushdown Automata 9. Compilers and Formal Languages 11 Context-Sensitive Languages 1. The Chomsky Hierarchy 2. Linear Bounded Automata 3. Closure Properties Part 3 Logic 12 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 13 Quantification Theory 1. The Language of Predicate Logic 2. Semantics 3. Logical Consequence 4. Herbrand’ s Theorem 5. Unification 6. Compactness and Countability *7. Godel’ s Incompleteness Theorem *8. Unsolvability of the Satisfiability Problem in Predicate Logic Part 4 Complexity 14 Abstract Complexity 1. The Blum Axioms 2. The Gap Theorem 3. Preliminary Form of the Speedup Theorem 4. The Speedup Theorem Concluded 15 Polynomial-Time Computability 1. Rates of Growth 2. P versus NP 3. Cook’ s Theorem 4. Other NP-Complete Problems Part 5 Semantics 16 Approximation Orderings 1. Programming Language Semantics 2. Partial Orders 3. Complete Partial Orders 4. Continuous Functions 5. Fixed Points 17 Denotational Semantics of Recursion Equations 1. Syntax 2. Semantics of Terms 3. Solutions to W-Programs 4. Denotational Semantics of W-Programs 5. Simple Data Structure Systems 6. Infinitary Data Structure Systems 18 Operational Semantics of Recursion Equations 1. Operational Semantics for Simple Data Structure Systems 2. Computable Functions 3. Operational Semantics for Infinitary Data Structure Systems

暂无相关目录，正在全力查找中！

暂无相关内容，正在全力查找中

暂无其它内容！

暂时还没有人为这本书评论！