Computability Theory: An Introduction to Recursion Theory

✍ Scribed by Herbert B. Enderton

• Publisher: Academic Press
• Year: 2010
• Tongue: English
• Leaves: 187
• Edition: 1
• Category: Library

✦ Synopsis

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  

✦ Table of Contents

Cover......Page 1
Computability Theory: An Introduction to Recursion Theory......Page 4
Copyright......Page 5
Dedication......Page 6
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
C......Page 178
E......Page 180
I......Page 181
N......Page 182
P......Page 183
R......Page 184
S......Page 185
U......Page 186
Z......Page 187