Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Computability Theory
 
Rebecca Weber Dartmouth College, Hanover, NH
Front Cover for Computability Theory
Available Formats:
Softcover ISBN: 978-0-8218-7392-2
Product Code: STML/62
203 pp 
List Price: $40.00
Individual Price: $32.00
Electronic ISBN: 978-0-8218-8543-7
Product Code: STML/62.E
203 pp 
List Price: $37.00
Individual Price: $29.60
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $60.00
Front Cover for Computability Theory
Click above image for expanded view
  • Front Cover for Computability Theory
  • Back Cover for Computability Theory
Computability Theory
Rebecca Weber Dartmouth College, Hanover, NH
Available Formats:
Softcover ISBN:  978-0-8218-7392-2
Product Code:  STML/62
203 pp 
List Price: $40.00
Individual Price: $32.00
Electronic ISBN:  978-0-8218-8543-7
Product Code:  STML/62.E
203 pp 
List Price: $37.00
Individual Price: $29.60
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $60.00
  • Book Details
     
     
    Student Mathematical Library
    Volume: 622012
    MSC: 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 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.

    Readership

    Undergraduate 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
  • 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
  • Request Review Copy
  • Get Permissions
Volume: 622012
MSC: 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 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.

Readership

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 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
You may be interested in...
Please select which format for which you are requesting permissions.