Computability Theory: An Introduction to Recursion Theory, provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The text includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable way.Frequent historical information presented throughout More extensive motivation for each of the topics than other texts currently available Connects with topics not included in other textbooks, such as complexity theory
Author(s): Herbert B. Enderton
Edition: 1
Publisher: Academic Press
Year: 2010
Language: English
Pages: 187
Contents......Page 8
Foreword......Page 10
Preface......Page 12
1.1.1 Decidable Sets......Page 14
1.1.2 Calculable Functions......Page 16
1.1.3 Church's Thesis......Page 23
Exercises......Page 24
1.2 Formalizations – An Overview......Page 25
1.2.1 Turing Machines......Page 26
1.2.2 Primitive Recursiveness and Search......Page 31
1.2.3 Loop and While Programs......Page 33
1.2.4 Register Machines......Page 35
1.2.5 Definability in Formal Languages......Page 37
1.2.6 Church's Thesis Revisited......Page 39
Exercises......Page 40
2.1 Primitive Recursive Functions......Page 42
2.1.1 Bounded Search......Page 53
2.2 Search Operation......Page 60
Exercises......Page 62
3.1 Register Machines......Page 66
3.2 A Universal Program......Page 73
Exercises......Page 84
3.3 Register Machines Over Words......Page 85
3.4 Binary Arithmetic......Page 89
4. Recursive Enumerability......Page 92
4.1 Recursively Enumerable Relations......Page 94
Exercises......Page 105
4.2 Parameters......Page 106
Exercises......Page 113
5.1 Arithmetical Hierarchy......Page 116
5.2 Definability in Arithmetic......Page 124
5.3 The Complexity of Truth......Page 129
Exercises......Page 133
6.1 Relative Computability......Page 134
6.2 Equivalence Relations......Page 140
6.3 Preordering Relations......Page 143
6.4 Ordering Degrees......Page 144
6.5 Structure of the Degrees......Page 145
Exercises......Page 150
7.1 Feasible Computability......Page 152
7.2 P versus NP......Page 160
7.3 Some Other Complexity Classes......Page 161
Exercises......Page 162
A1. Mathspeak......Page 164
A2. Countability......Page 168
A3. Decadic Notation......Page 172
References......Page 176
ABC......Page 178
DE......Page 180
FGHI......Page 181
JKLMN......Page 182
OP......Page 183
QR......Page 184
S......Page 185
TU......Page 186
VWZ......Page 187
