Computability Theory: An Introduction to Recursion Theory

Front Cover
Academic Press, Dec 30, 2010 - Computers - 192 pages
0 Reviews

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
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Chapter 1 The Computability Concept
1
Chapter 2 General Recursive Functions
29
Chapter 3 Programs and Machines
53
Chapter 4 Recursive Enumerability
79
Chapter 5 Connections to Logic
103
Chapter 6 Degrees of Unsolvability
121
Chapter 7 PolynomialTime Computability
139
Appendix 1 Mathspeak
151
Appendix 2 Countability
155
Appendix 3 Decadic Notation
159
References
163
Index
165
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information