Computability Theory: An Introduction to Recursion Theory

✍ Scribed by Herbert B. Enderton

• Publisher: Academic Press
• Year: 2010
• Tongue: English
• Leaves: 176
• 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

Computability Theory......Page 2
Copyright......Page 3
Dedication......Page 4
Foreword......Page 5
Preface......Page 6
Decidable Sets......Page 7
Calculable Functions......Page 9
Church's Thesis......Page 16
Exercises......Page 17
Formalizations – An Overview......Page 18
Turing Machines......Page 19
Primitive Recursiveness and Search......Page 24
Loop and While Programs......Page 26
Register Machines......Page 28
Definability in Formal Languages......Page 30
Church's Thesis Revisited......Page 32
Exercises......Page 33
Primitive Recursive Functions......Page 34
Bounded Search......Page 45
Search Operation......Page 52
Exercises......Page 54
Register Machines......Page 57
A Universal Program......Page 64
Exercises......Page 75
Register Machines Over Words......Page 76
Binary Arithmetic......Page 80
Recursive Enumerability......Page 82
Recursively Enumerable Relations......Page 84
Exercises......Page 95
Parameters......Page 96
Exercises......Page 103
Arithmetical Hierarchy......Page 106
Definability in Arithmetic......Page 114
The Complexity of Truth......Page 119
Exercises......Page 123
Relative Computability......Page 124
Equivalence Relations......Page 130
Preordering Relations......Page 133
Ordering Degrees......Page 134
Structure of the Degrees......Page 135
Exercises......Page 140
Feasible Computability......Page 142
P versus NP......Page 150
Some Other Complexity Classes......Page 151
Exercises......Page 152
Mathspeak......Page 153
Countability......Page 157
Decadic Notation......Page 161
References......Page 165
C......Page 167
E......Page 169
I......Page 170
N......Page 171
P......Page 172
R......Page 173
S......Page 174
U......Page 175
Z......Page 176

✦ Subjects

Математика;Вычислительная математика;