Davis / Weyuker / Rheinboldt Computability, Complexity, and Languages

Fundamentals of Theoretical Computer Science
1. Auflage 2014
ISBN: 978-1-4832-6458-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 446 Seiten, Web PDF

Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science provides an introduction to the various aspects of theoretical computer science. Theoretical computer science is the mathematical study of models of computation. This text is composed of five parts encompassing 17 chapters, and begins with an introduction to the use of proofs in mathematics and the development of computability theory in the context of an extremely simple abstract programming language. The succeeding parts demonstrate the performance of abstract programming language using a macro expansion technique, along with presentations of the regular and context-free languages. Other parts deal with the aspects of logic that are important for computer science and the important theory of computational complexity, as well as the theory of NP-completeness. The closing part introduces the advanced recursion and polynomial-time computability theories, including the priority constructions for recursively enumerable Turing degrees. This book is intended primarily for undergraduate and graduate mathematics students.

Autoren/Hrsg.

Davis, Martin D.

Weyuker, Elaine J.

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science;4
3;Copyright Page;5
4;Table of Contents;8
5;Dedication;6
6;Preface;14
7;Acknowledgments;18
8;Dependency Graph;20
9;CHAPTER 1. Preliminaries;22
9.1;1. Sets and n-tuples;22
9.2;2. Functions;23
9.3;3. Alphabets and Strings;24
9.4;4. Predicates;25
9.5;5. Quantifiers;27
9.6;6. Proof by Contradiction;28
9.7;7. Mathematical Induction;30
10;PART 1: COMPUTABILITY;34
10.1;CHAPTER 2. Programs and Computable Functions;36
10.1.1;1. A Programming Language;36
10.1.2;2. Some Examples of Programs;37
10.1.3;3. Syntax;44
10.1.4;4. Computable Functions;46
10.1.5;5. More about Macros;49
10.2;CHAPTER 3. Primitive Recursive Functions;53
10.2.1;1. Composition;53
10.2.2;2. Recursion;54
10.2.3;3. PRC Classes;55
10.2.4;4. Some Primitive Recursive Functions;57
10.2.5;5. Primitive Recursive Predicates;60
10.2.6;6. Iterated Operations and Bounded Quantifiers;62
10.2.7;7. Minimalization;64
10.2.8;8. Pairing Functions and Gödel Numbers;68
10.3;CHAPTER 4. A Universal Program;72
10.3.1;1. Coding Programs by Numbers;72
10.3.2;2. The Halting Problem;74
10.3.3;3. Universality;76
10.3.4;4. Recursively Enumerable Sets;81
10.3.5;5. The Parameter Theorem;85
10.3.6;6. The Recursion Theorem;87
10.3.7;7. Rice's Theorem;88
10.4;CHAPTER 5. Calculations on Strings;91
10.4.1;1. Numerical Representation of Strings;91
10.4.2;2. A Programming Language for String Computations;98
10.4.3;3. The Languages ¥ and £f n;102
10.4.4;4. Post-Turing Programs;103
10.5;CHAPTER 6. Turing Machines;118
10.5.1;1. Internal States;118
10.5.2;2. A Universal Turing Machine;124
10.5.3;3. The Languages Accepted by Turing Machines;125
10.5.4;4. The Halting Problem for Turing Machines;128
10.5.5;5. Nondeterministic Turing Machines;129
10.5.6;6. Variations on the Turing Machine Theme;132
10.6;CHAPTER 7. Processes and Grammars;139
10.6.1;1. Semi-Thue Processes;139
10.6.2;2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes;140
10.6.3;3. Unsolvable Word Problems;145
10.6.4;4. Post's Correspondence Problem;149
10.6.5;5. Grammars;154
10.6.6;6. Some Unsolvable Problems Concerning Grammars;158
10.6.7;7. Recursion and Minimalization;159
10.6.8;8. Normal Processes;163
10.6.9;9. A Non-R.E. Set;166
11;PART 2: GRAMMARS AND AUTOMATA;168
11.1;CHAPTER 8. Regular Languages;170
11.1.1;1. Finite Automata;170
11.1.2;2. Nondeterministic Finite Automata;174
11.1.3;3. Additional Examples;177
11.1.4;4. Closure Properties;179
11.1.5;5. Kleene's Theorem;182
11.1.6;6. The Pumping Lemma and Its Applications;187
11.1.7;7. The Myhill-Nerode Theorem;189
11.2;CHAPTER 9. Context-Free Languages;192
11.2.1;1. Context-Free Grammars and Their Derivation Trees;192
11.2.2;2. Regular Grammars;202
11.2.3;3. Chomsky Normal Form;206
11.2.4;4. Bar-Hillel's Pumping Lemma;208
11.2.5;5. Closure Properties;211
11.2.6;6. Solvable and Unsolvable Problems;216
11.2.7;7. Bracket Languages;220
11.2.8;8. Pushdown Automata;225
11.2.9;9. Compilers and Formal Languages;235
11.3;CHAPTER 10. Context-Sensitive Languages;239
11.3.1;1. The Chomsky Hierarchy;239
11.3.2;2. Linear Bounded Automata;241
11.3.3;3. Closure Properties;247
12;PART 3: LOGIC;250
12.1;CHAPTER 11. Propositional Calculus;252
12.1.1;1. Formulas and Assignments;252
12.1.2;2. Tautological Inference;256
12.1.3;3. Normal Forms;257
12.1.4;4. The Davis-Putnam Rules;263
12.1.5;5. Minimal Unsatisfiability and Subsumption;268
12.1.6;6. Resolution;268
12.1.7;7. The Compactness Theorem;271
12.2;CHAPTER 12. Quantification Theory;274
12.2.1;1. The Language of Predicate Logic;274
12.2.2;2. Semantics;276
12.2.3;3. Logical Consequence;279
12.2.4;4. Herbrand's Theorem;284
12.2.5;5. Unification;295
12.2.6;6. Compactness and Countability;299
12.2.7;7. Gödel's Incompleteness Theorem;301
12.2.8;8. Unsolvability of the Satisfiability Problem in Predicate Logic;304
13;PART 4: COMPLEXITY;310
13.1;CHAPTER 13. Loop Programs;312
13.1.1;1. The Language L and Primitive Recursive Functions;312
13.1.2;2. Running Time;318
13.1.3;3. S£n as a Hierarchy;324
13.1.4;4. A Converse to the Bounding Theorem;328
13.1.5;5. Doing without Branch Instructions;332
13.2;CHAPTER 14. Abstract Complexity;334
13.2.1;1. The Blum Axioms;334
13.2.2;2. The Gap Theorem;338
13.2.3;3. Preliminary Form of the Speedup Theorem;340
13.2.4;4. The Speedup Theorem Concluded;347
13.3;CHAPTER 15. Polynomial-Time Computability;352
13.3.1;1. Rates of Growth;352
13.3.2;2. P versus NP;356
13.3.3;3. Cook's Theorem;362
13.3.4;4. Other NP-Complete Problems;367
14;PART 5: UNSOLVABILITY;372
14.1;CHAPTER 16. Classifying Unsolvable Problems;374
14.1.1;1. Using Oracles;374
14.1.2;2. Relativization of Universality;377
14.1.3;3. Reducibility;383
14.1.4;4. Sets R.E. Relative to an Oracle;387
14.1.5;5. The Arithmetic Hierarchy;391
14.1.6;6. Post's Theorem;393
14.1.7;7. Classifying Some Unsolvable Problems;399
14.1.8;8. Rice's Theorem Revisited;405
14.1.9;9. Recursive Permutations;406
14.2;CHAPTER 17. Degrees of Unsolvability and Post's Problem;410
14.2.1;1. Turing Degrees;410
14.2.2;2. The Kleene-Post Theorem;413
14.2.3;3. Creative Sets—Myhill's Theorem;417
14.2.4;4. Simple Sets—Dekker's Theorem;424
14.2.5;5. Sacks's Splitting Theorem;429
14.2.6;6. The Priority Method;431
15;Suggestions for Further Reading;438
16;Index;440
17;Computer Science and Applied Mathematics: A SERIES OF MONOGRAPHS AND TEXTBOOKS;447