Computability

1. Front Matter

   Pages i-xi

   PDF

2. Preliminaries

   • Douglas S. Bridges

   Pages 1-4

3. What Is a Turing Machine?

   • Douglas S. Bridges

   Pages 5-17

4. Computable Partial Functions

   • Douglas S. Bridges

   Pages 19-33

5. Effective Enumerations

   • Douglas S. Bridges

   Pages 35-45

6. Computable Numbers and Functions

   • Douglas S. Bridges

   Pages 47-74

7. Rice’s Theorem and the Recursion Theorem

   • Douglas S. Bridges

   Pages 75-91

8. Abstract Complexity Theory

   • Douglas S. Bridges

   Pages 93-115

9. Back Matter

   Pages 117-180

   PDF

Aimed at mathematicians and computer scientists who will only be exposed to one course in this area, Computability: A Mathematical Sketchbook provides a brief but rigorous introduction to the abstract theory of computation, sometimes also referred to as recursion theory. It develops major themes in computability theory, such as Rice's theorem and the recursion theorem, and provides a systematic account of Blum's complexity theory as well as an introduction to the theory of computable real numbers and functions. The book is intended as a university text, but it may also be used for self-study; appropriate exercises and solutions are included.

• complexity
• computability
• function
• recursion
• theorem

• Department of Mathematics, University of Waikato, Hamilton, New Zealand

  Douglas S. Bridges

Policies and ethics