文档介绍：Second Edition
Computability,
Complexity, and
Languages
Fundamentals of
puter Science
Martin D. Davis
Department puter Science
Courant Institute of Mathematical Sciences
New York University
New York, New York
Ron Sigal
Departments of Mathematics puter Science
Yale University
New Haven, Connecticut
Elaine J. Weyuker
Department puter Science
Courant Institute of Mathematical Sciences
New York University
New York, New York
j= ,.”
ACADEMIC PRESS
Harcourt, Brace & Company
Boston San Diego New York
London Sydney Tokyo Toronto
Contents
. . .
Preface xl11
Acknowledgments xvii
Dependency Graph xix
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 Cmnputability
2 Programs putable 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
vii
Contents
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 Gijdel 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. putable Function That Is Not Primitive Recursive 105
5 Calculations on Strings 113
1. Numerical Representation of Strings 113
2. A Programming Language for putations 121
3. The Languages Y and Yn 126
4. Post-Turing Programs 129
5. Simulation of-F”, in 9 135
6. Simulation of Yin Y 140
6 Turing Machines 145
1. Internal States 145
2. A Universal Turing Machine 152
3. The Languages Accepted