计算理论基础：可计算性、复杂性和语言（英文版·第2版）
Contents
I Preliminaries 1
1. Sets and n-tuples 1
2. Functions 3
3. Alphabets and Strings 4
4. Predicates 5
5. Quantifiers 6
6. Proof by Contradiction 8
7. Mathematical Induction 9
Part 1 Computability 15
2 Programs and Computable Functions 17
1. A Programming Language 17
2. Some Examples of Programs 18
3. Syntax 25
4. Computable Functions 28
5. More about Macros 32
3 Primitive Recursive Functions 39
1. Composition 39
2. Recursion 40
3. PRC Classes 42
4. Some Primitive Recursive Functions 44
5. Primitive Recursive Predicates 49
6. Iterated Operations and Bounded Quantifiers 52
7. Minimalization 55
8. Pairing Functions and G6del Numbers 59
4 A Universal Program 65
1. Coding Programs by Numbers 65
2. The Halting Problem 68
3. Universality 70
4. Recursively Enumerable Sets 78
5. The Parameter Theorem 85
6. Diagonalization and Reducibility 88
7. Rice s Theorem 95
*8. The Recursion Theorem 97
*9. A Computable Function That Is Not Primitive Recursive 105
5 Calculations on Strings 113
1. Numerical Representation of Strings 113
2. A Programming Language for String Computations 121
3. The Languages and n 126
4. Post-Turing Programs 129
5. Simulation of n in 135
6. Simulation of in 140
6 Turing Machines 145
1. Internal States 145
2. A Universal Turing Machine 152
3. The Languages Accepted by Turing Machines 153
4. The Halting Problem for Turing Machines 157
5. Nondeterministic Turing Machines 159
6. Variations on the Turing Machine Theme 162
7 Processes and Grammars 169
1. Semi-Thue Processes 169
2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes 171
3. Unsolvable Word Problems 176
4. Posts Correspondence Problem 181
5. Grammars 186
6. Some Unsolvable Problems Concerning Grammars 191
7. Normal Processes 192
8 Classifying Unsolvable Problems 197
1. Using Oracles 197
2. Relativization of Universality 201
3. Reducibility 207
4. Sets r.e. Relative to an Oracle 211
5. The Arithmetic Hierarchy 215
6. Posts Theorem 217
7. Classifying Some Unsolvable Problems 224
8. Rices Theorem Revisited 230
9. Recursive Permutations 231
Part 2 Grammars and Automata 235
9 Regular Languages 237
1. Finite Automata 237
2. Nondeterministic Finite Automata 242
3. Additional Examples 247
4. Closure Properties 249
5. Kleenes Theorem 253
6. The Pumping Lemma and Its Applications 260
7. The Myhill-Nerode Theorem 263
10 Context-Free Languages 269
1. Context-Free Grammars and Their Derivation Trees 269
2. Regular Grammars 280
3. Chomsky Normal Form 285
4. Bar-Hillels Pumping Lemma 287
5. Closure Properties 291
*6. Solvable and Unsolvable Problems 297
7. Bracket Languages 301
8. Pushdown Automata 308
9. Compilers and Formal Languages 323
11 Context-Sensitive Languages 327
1. The Chomsky Hierarchy 327
2. Linear Bounded Automata 330
3. Closure Properties 337
Part 3 Logic 345
12 Propositional Calculus 347
1. Formulas and Assignments 347
2. Tautological Inference 352
3. Normal Forms 353
4. The Davis-Putnam Rules 360
5. Minimal Unsatisfiability and Subsumption 366
6. Resolution 367
7. The Compactness Theorem 370
13 Quantification Theory 375
1. The Language of Predicate Logic 375
2. Semantics 377
3. Logical Consequence 382
4. Herbrands Theorem 388
5. Unification 399
6. Compactness and Countability 404
*7. G6dels Incompleteness Theorem 407
*8. Unsolvability of the Satisfiability Problem in Predicate Logic 410
Part 4 Complexity 417
14 Abstract Complexity 419
1. The Blum Axioms 419
2. The Gap Theorem 425
3. Preliminary Form of the Speedup Theorem 428
4. The Speedup Theorem Concluded 435
15 Polynomial-Time Computability 439
1. Rates of Growth 439
2. P versus NP 443
3. Cooks Theorem 451
4. Other NP-Complete Problems 457
Part 5 Semantics 465
16 Approximation Orderings 467
1. Programming Language Semantics 467
2. Partial Orders 472
3. Complete Partial Orders 475
4. Continuous Functions 486
5. Fixed Points 494
17 Denotational Semantics of Recursion Equations 505
1. Syntax 505
2. Semantics of Terms 511
3. Solutions to W-Programs 520
4. Denotational Semantics of W-Programs 530
5. Simple Data Structure Systems 539
6. Infinitary Data Structure Systems 544
18 Operational Semantics of Recursion Equations 557
1. Operational Semantics for Simple Data Structure Systems 557
2. Computable Functions 575
3. Operational Semantics for lnfinitary Data Structure Systems 584
Suggestions for Further Reading 593
Notation Index 595
Index 599
I Preliminaries 1
1. Sets and n-tuples 1
2. Functions 3
3. Alphabets and Strings 4
4. Predicates 5
5. Quantifiers 6
6. Proof by Contradiction 8
7. Mathematical Induction 9
Part 1 Computability 15
2 Programs and Computable Functions 17
1. A Programming Language 17
2. Some Examples of Programs 18
3. Syntax 25
4. Computable Functions 28
5. More about Macros 32
3 Primitive Recursive Functions 39
1. Composition 39
2. Recursion 40
3. PRC Classes 42
4. Some Primitive Recursive Functions 44
5. Primitive Recursive Predicates 49
6. Iterated Operations and Bounded Quantifiers 52
7. Minimalization 55
8. Pairing Functions and G6del Numbers 59
4 A Universal Program 65
1. Coding Programs by Numbers 65
2. The Halting Problem 68
3. Universality 70
4. Recursively Enumerable Sets 78
5. The Parameter Theorem 85
6. Diagonalization and Reducibility 88
7. Rice s Theorem 95
*8. The Recursion Theorem 97
*9. A Computable Function That Is Not Primitive Recursive 105
5 Calculations on Strings 113
1. Numerical Representation of Strings 113
2. A Programming Language for String Computations 121
3. The Languages and n 126
4. Post-Turing Programs 129
5. Simulation of n in 135
6. Simulation of in 140
6 Turing Machines 145
1. Internal States 145
2. A Universal Turing Machine 152
3. The Languages Accepted by Turing Machines 153
4. The Halting Problem for Turing Machines 157
5. Nondeterministic Turing Machines 159
6. Variations on the Turing Machine Theme 162
7 Processes and Grammars 169
1. Semi-Thue Processes 169
2. Simulation of Nondeterministic Turing Machines by Semi-Thue Processes 171
3. Unsolvable Word Problems 176
4. Posts Correspondence Problem 181
5. Grammars 186
6. Some Unsolvable Problems Concerning Grammars 191
7. Normal Processes 192
8 Classifying Unsolvable Problems 197
1. Using Oracles 197
2. Relativization of Universality 201
3. Reducibility 207
4. Sets r.e. Relative to an Oracle 211
5. The Arithmetic Hierarchy 215
6. Posts Theorem 217
7. Classifying Some Unsolvable Problems 224
8. Rices Theorem Revisited 230
9. Recursive Permutations 231
Part 2 Grammars and Automata 235
9 Regular Languages 237
1. Finite Automata 237
2. Nondeterministic Finite Automata 242
3. Additional Examples 247
4. Closure Properties 249
5. Kleenes Theorem 253
6. The Pumping Lemma and Its Applications 260
7. The Myhill-Nerode Theorem 263
10 Context-Free Languages 269
1. Context-Free Grammars and Their Derivation Trees 269
2. Regular Grammars 280
3. Chomsky Normal Form 285
4. Bar-Hillels Pumping Lemma 287
5. Closure Properties 291
*6. Solvable and Unsolvable Problems 297
7. Bracket Languages 301
8. Pushdown Automata 308
9. Compilers and Formal Languages 323
11 Context-Sensitive Languages 327
1. The Chomsky Hierarchy 327
2. Linear Bounded Automata 330
3. Closure Properties 337
Part 3 Logic 345
12 Propositional Calculus 347
1. Formulas and Assignments 347
2. Tautological Inference 352
3. Normal Forms 353
4. The Davis-Putnam Rules 360
5. Minimal Unsatisfiability and Subsumption 366
6. Resolution 367
7. The Compactness Theorem 370
13 Quantification Theory 375
1. The Language of Predicate Logic 375
2. Semantics 377
3. Logical Consequence 382
4. Herbrands Theorem 388
5. Unification 399
6. Compactness and Countability 404
*7. G6dels Incompleteness Theorem 407
*8. Unsolvability of the Satisfiability Problem in Predicate Logic 410
Part 4 Complexity 417
14 Abstract Complexity 419
1. The Blum Axioms 419
2. The Gap Theorem 425
3. Preliminary Form of the Speedup Theorem 428
4. The Speedup Theorem Concluded 435
15 Polynomial-Time Computability 439
1. Rates of Growth 439
2. P versus NP 443
3. Cooks Theorem 451
4. Other NP-Complete Problems 457
Part 5 Semantics 465
16 Approximation Orderings 467
1. Programming Language Semantics 467
2. Partial Orders 472
3. Complete Partial Orders 475
4. Continuous Functions 486
5. Fixed Points 494
17 Denotational Semantics of Recursion Equations 505
1. Syntax 505
2. Semantics of Terms 511
3. Solutions to W-Programs 520
4. Denotational Semantics of W-Programs 530
5. Simple Data Structure Systems 539
6. Infinitary Data Structure Systems 544
18 Operational Semantics of Recursion Equations 557
1. Operational Semantics for Simple Data Structure Systems 557
2. Computable Functions 575
3. Operational Semantics for lnfinitary Data Structure Systems 584
Suggestions for Further Reading 593
Notation Index 595
Index 599
Martin D．Davis，著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门（导师均为计算科学大师Alonzo Church）。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post-Turing机更使其声名远播。除本书外，他还著有经典名著Computability and Unsolvability。
Ron Sigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。
Elaine J．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT＆T院士、ACM妇女委员会主席、ACM执行委员，现任AT＆T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。
Ron Sigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。
Elaine J．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT＆T院士、ACM妇女委员会主席、ACM执行委员，现任AT＆T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。
《计算理论基础可计算性复杂性和语言(英文版·第2版)》是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性(包括NP完全问题)和编程语言的语义等主题，并展示了它们之间如何相互关联。《计算理论基础可计算性复杂性和语言(英文版·第2版)》是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。
比价列表
公众号、微信群
缺书网微信公众号
扫码进群实时获取购书优惠