计算理论基础：可计算性、复杂性和语言(英文版·第2版)
点此进入淘宝搜索页搜索分类: 图书,计算机/网络,计算机理论,
作者： （美）戴维斯（Davis，M.D.），（美）西加尔（Sigal，R.），（美）韦约克（Weyuker，E.J.） 著
出 版 社： 人民邮电出版社
出版时间： 2009-5-1字数：版次： 1页数： 609印刷时间：开本： 16开印次：纸张：I S B N ： 9787115196576包装： 平装编辑推荐
“如果说有哪一本计算理论方面的书所有的大学图书馆都应该收藏，那就是这本书!”
——Choice杂志
作者简介：
Martin D.Davis 著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门（导师均为计算科学大师Alonzo Church）。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post—Turin9机更使其声名远播。除本书外，他还著有经典名著Computability and Unsolvability。
内容简介
本书是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性（包括NP完全问题）和编程语言的语义等主题，并展示了它们之间如何相互关联。
本书是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。
目录
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
