計算理論基礎：可計算性、複雜性和語言(英

《計算理論基礎：可計算性、複雜性和語言》是2009年5月1日人民郵電出版社出版的一本圖書，作者是(美國)Maritin D.Davis，(美國)Ron Sigal，(美國)Elaine J.Weyuker。

基本介紹

• 書名：計算理論基礎可計算性複雜性和語言(英文版·第2版)
• 作者：(美國)Maritin D.Davis，(美國)Ron Sigal，(美國)Elaine J.Weyuker
• ISBN：9787115196576
• 頁數：607頁
• 出版社：人民郵電出版社
• 出版時間：2009年5月1日
• 裝幀：平裝
• 開本：16
• 叢書名：圖靈原版計算機科學系列

內容簡介

《計算理論基礎可計算性複雜性和語言(英文版·第2版)》是理論計算機科學領域的名作，是計算機科學核心主題的導論性教材。全書分為可計算性、文法與自動機、邏輯學、複雜性及語義學5個部分，分別講述了可計算性理論、形式語言、邏輯學與自動演繹、可計算複雜性(包括NP完全問題)和程式語言的語義等主題，並展示了它們之間如何相互關聯。《計算理論基礎可計算性複雜性和語言(英文版·第2版)》是計算機及相關專業高年級本科生和研究生的理想教學參考書，對於計算機領域的專業人士也是很好的技術參考書

作者簡介

作者：(美國)Maritin D.Davis (美國)Ron Sigal (美國)Elaine J.Weyuker

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年。

媒體評論

“如果說有哪一本計算理論方面的書所有的大學圖書館都應該收藏，那就是這本書！”

——Choice雜誌

目錄信息

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. Post's 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. Post's Theorem 217

7. Classifying Some Unsolvable Problems 224

8. Rice's 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. Kleene's 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-Hillel's 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. Herbrand's Theorem 388

5. Unification 399

6. Compactness and Countability 404

*7. G6del's 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. Cook's 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