**Student Mathematical Library**

Volume: 62;
2012;
203 pp;
Softcover

MSC: Primary 03;
Secondary 68

Print ISBN: 978-0-8218-7392-2

Product Code: STML/62

List Price: $37.00

Individual Price: $29.60

**Electronic ISBN: 978-0-8218-8543-7
Product Code: STML/62.E**

List Price: $37.00

Individual Price: $29.60

#### You may also like

#### Supplemental Materials

# Computability Theory

Share this page
*Rebecca Weber*

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 self-contained, 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.

#### Table of Contents

# Table of Contents

## Computability Theory

- Cover Cover11 free
- Title page iii4 free
- Contents v6 free
- Introduction 110 free
- Background 918 free
- Defining computability 4150
- Working with computable functions 7786
- Computing and enumerating sets 95104
- Turing reduction and Post’s problem 109118
- Two hierarchies of sets 127136
- Further tools and results 139148
- Areas of research 149158
- Mathematical asides 189198
- Bibliography 193202
- Index 199208 free
- Back Cover Back Cover1218

#### Readership

Undergraduate students interested in computability theory and recursion theory.

#### 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 one-term 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