Softcover ISBN:  9780821873922 
Product Code:  STML/62 
List Price:  $59.00 
Individual Price:  $47.20 
eBook ISBN:  9780821885437 
Product Code:  STML/62.E 
List Price:  $49.00 
Individual Price:  $39.20 
Softcover ISBN:  9780821873922 
eBook: ISBN:  9780821885437 
Product Code:  STML/62.B 
List Price:  $108.00 $83.50 
Softcover ISBN:  9780821873922 
Product Code:  STML/62 
List Price:  $59.00 
Individual Price:  $47.20 
eBook ISBN:  9780821885437 
Product Code:  STML/62.E 
List Price:  $49.00 
Individual Price:  $39.20 
Softcover ISBN:  9780821873922 
eBook ISBN:  9780821885437 
Product Code:  STML/62.B 
List Price:  $108.00 $83.50 

Book DetailsStudent Mathematical LibraryVolume: 62; 2012; 203 ppMSC: Primary 03; Secondary 68
What can we compute—even with unlimited resources? Is everything within reach? Or are computations necessarily drastically limited, not just in practice, but theoretically? These questions are at the heart of computability theory.
The goal of this book is to give the reader a firm grounding in the fundamentals of computability theory and an overview of currently active areas of research, such as reverse mathematics and algorithmic randomness. Turing machines and partial recursive functions are explored in detail, and vital tools and concepts including coding, uniformity, and diagonalization are described explicitly. From there the material continues with universal machines, the halting problem, parametrization and the recursion theorem, and thence to computability for sets, enumerability, and Turing reduction and degrees. A few more advanced topics round out the book before the chapter on areas of research. The text is designed to be selfcontained, with an entire chapter of preliminary material including relations, recursion, induction, and logical and set notation and operators. That background, along with ample explanation, examples, exercises, and suggestions for further reading, make this book ideal for independent study or courses with few prerequisites.
ReadershipUndergraduate students interested in computability theory and recursion theory.

Table of Contents

Chapters

Chapter 1. Introduction

Chapter 2. Background

Chapter 3. Defining computability

Chapter 4. Working with computable functions

Chapter 5. Computing and enumerating sets

Chapter 6. Turing reduction and Post’s problem

Chapter 7. Two hierarchies of sets

Chapter 8. Further tools and results

Chapter 9. Areas of research

Appendix A. Mathematical asides


Additional Material

Reviews

This is only a 200 page book, but it covers a wealth of material...[A] clear, concise introduction that would be ideal for a oneterm undergraduate course...Recommended.
CHOICE 
This short text does an excellent job of covering those topics that should be included in an undergraduate introduction to computability theory... There are both appropriate exercises and enticing doorways to open topics and current research. The exposition is precise, but still conversational. I believe my students will enjoy reading this text.
Jeffry L. Hirst, Zentralblatt MATH


RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
What can we compute—even with unlimited resources? Is everything within reach? Or are computations necessarily drastically limited, not just in practice, but theoretically? These questions are at the heart of computability theory.
The goal of this book is to give the reader a firm grounding in the fundamentals of computability theory and an overview of currently active areas of research, such as reverse mathematics and algorithmic randomness. Turing machines and partial recursive functions are explored in detail, and vital tools and concepts including coding, uniformity, and diagonalization are described explicitly. From there the material continues with universal machines, the halting problem, parametrization and the recursion theorem, and thence to computability for sets, enumerability, and Turing reduction and degrees. A few more advanced topics round out the book before the chapter on areas of research. The text is designed to be selfcontained, with an entire chapter of preliminary material including relations, recursion, induction, and logical and set notation and operators. That background, along with ample explanation, examples, exercises, and suggestions for further reading, make this book ideal for independent study or courses with few prerequisites.
Undergraduate students interested in computability theory and recursion theory.

Chapters

Chapter 1. Introduction

Chapter 2. Background

Chapter 3. Defining computability

Chapter 4. Working with computable functions

Chapter 5. Computing and enumerating sets

Chapter 6. Turing reduction and Post’s problem

Chapter 7. Two hierarchies of sets

Chapter 8. Further tools and results

Chapter 9. Areas of research

Appendix A. Mathematical asides

This is only a 200 page book, but it covers a wealth of material...[A] clear, concise introduction that would be ideal for a oneterm undergraduate course...Recommended.
CHOICE 
This short text does an excellent job of covering those topics that should be included in an undergraduate introduction to computability theory... There are both appropriate exercises and enticing doorways to open topics and current research. The exposition is precise, but still conversational. I believe my students will enjoy reading this text.
Jeffry L. Hirst, Zentralblatt MATH