Computability, Complexity, and Languages · Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing) by Davis, Martin -- Read -- Imperial Library of Trantor

Index

Title page Table of Contents Copyright Dedication Preface Acknowledgments Dependency Graph Chapter 1: Preliminaries

1. Sets and n-tuples 2. Functions 3. Alphabets and Strings 4. Predicates 5. Quantifiers 6. Proof by Contradiction Exercises 7. Mathematical Induction Exercises

Part 1: Computability

Chapter 2: Programs and Computable Functions

1. A Programming Language 2. Some Examples of Programs Exercises 3. Syntax Exercises 4. Computable Functions Exercises 5. More about Macros Exercises

Chapter 3: Primitive Recursive Functions

1 Composition 2. Recursion 3 PRC Classes Exercises 4. Some Primitive Recursive Functions Exercises 5. Primitive Recursive Predicates Exercise 6. Iterated Operations and Bounded Quantifiers Exercises 7. Minimalization Exercises 8. Pairing Functions and Gödel Numbers Exercises

Chapter 4: A Universal Program

1. Coding Programs by Numbers 2. The Halting Problem Exercises 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

Chapter 5: Calculations on Strings

1. Numerical Representation of Strings 2. A Programming Language for String Computations 3. The Languages and 4. Post–Turing Programs 5. Simulation of in 6. Simulation of in

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 Exercises 2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes Exercises 3. Unsolvable Word Problems Exercises 4. Post’s Correspondence Problem Exercises 5. Grammars Exercises 6. Some Unsolvable Problems Concerning Grammars Exercise *7. Normal Processes Exercise

Chapter 8: Classifying Unsolvable Problems

1 Using Oracles Exercises 2. Relativization of Universality Exercises 3. Reducibility Exercises 4. Sets r.e. Relative to an Oracle Exercise 5. The Arithmetic Hierarchy 6. Post’s Theorem 7. Classifying Some Unsolvable Problems Exercises 8. Rice’s Theorem Revisited Exercises 9. Recursive Permutations Exercises

Part 2: Grammars and Automata

Chapter 9: Regular Languages

1. Finite Automata Exercises 2. Nondeterministic Finite Automata Exercises 3. Additional Examples 4. Closure Properties Exercises 5. Kleene’s Theorem Exercises 6. The Pumping Lemma and Its Applications Exercises 7. The Myhill - Nerode Theorem Exercises

Chapter 10: Context-Free Languages

1. Context-Free Grammars and Their Derivation Trees Exercises 2. Regular Grammars Definition. Exercises 3. Chomsky Normal Form Definition. Exercises 4. Bar-Hillel’s Pumping Lemma Exercises 5. Closure Properties Exercises *6. Solvable and Unsolvable Problems4 Lemma. Exercises 7. Bracket Languages Exercises 8. Pushdown Automata Definition. Exercises 9. Compilers and Formal Languages Exercise

Chapter 11: Context-Sensitive Languages

1. The Chomsky Hierarchy Exercises 2. Linear Bounded Automata Exercises 3. Closure Properties Exercises

Part 3: Logic

Chapter 12: Propositional Calculus

1. Formulas and Assignments Exercises 2. Tautological Inference Exercises 3. Normal Forms Exercises 4. The Davis-Putnam Rules Exercises 5. Minimal Unsatisfiability and Subsumption Exercise 6. Resolution Exercises 7. The Compactness Theorem Exercises

Chapter 13: Quantification Theory

1. The Language of Predicate Logic Exercises 2. Semantics Exercises 3. Logical Consequence Exercises 4. Herbrand’s Theorem EXAMPLE 1. EXAMPLE 2. EXAMPLE 3. Exercises 5. Unification Exercises 6. Compactness and Countability Exercises *7. Gödel’s Incompleteness Theorem Exercises *8. Unsolvability of the Satisfiability Problem in Predicate Logic Exercises

Part 4: Complexity

Chapter 14: Abstract Complexity

1 The Blum Axioms Exercises 2 The Gap Theorem Exercises 3. Preliminary Form of the Speedup Theorem 4. The Speedup Theorem Concluded Exercises

Chapter 15: Polynomial-Time Computability

1. Rates of Growth Exercises 2. P versus NP Exercises 3. Cook’s Theorem Exercises 4. Other NP-Complete Problems Exercises

Part 5: Semantics

Chapter 16: Approximation Orderings

1 Programming Language Semantics 2 Partial Orders 3 Complete Partial Orders 4. Continuous Functions 5. Fixed Points Definition.

Chapter 17: Denotational Semantics of Recursion Equations

1. Syntax Exercises 2. Semantics of Terms Exercises 3. Solutions to W-Programs Exercises 4. Denotational Semantics of W-Programs Exercises 5. Simple Data Structure Systems Exercises 6. Infinitary Data Structure Systems Exercises

Chapter 18: Operational Semantics of Recursion Equations

1. Operational Semantics for Simple Data Structure Systems Exercises 2. Computable Functions Exercises 3. Operational Semantics for Infinitary Data Structure Systems Exercises

Suggestions for Further Reading Notation Index Index