計算機理論基礎：可計算性、複雜性和語言（英文版·第2版）（簡體書）

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

“如果說有哪一本計算理論方面的書所有的大學圖書館都應該收藏，那就是這本書!” ——Choice雜志 作者簡介： Martin D.Davis 著名計算機科學家和數學家。1950年在普林斯頓大學獲得博士學位，與圖靈同門（導師均為計算科學大師Alonzo Church）。后長期任教于紐約大學柯朗數學研究所。他是自動演繹理論先驅，還是DPLL算法的發明人之一，Post—Turin9機更使其聲名遠播。除本書外，他還著有經典名著Computability and Unsolvability。

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 Computability
2 Programs and ComputableFunetions
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 Godel 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 * and *
4. Post-Turing Programs
5. Simulation of * in *
6. Simulation of * in *
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
8 Classifying Unsolvable Problems
Part 2 Grammars and Automate
Part 3 Logic
Part 4 Complexity
Part 5 Semantics