Aimed at mathematicians and computer scientists who will only be exposed to one course in this area, Computability: AMathematical 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.
Inhaltsverzeichnis
Preliminaries. - 1 What Is a Turing Machine? . - 2 Computable Partial Functions. - 3 Effective Enumerations. - 4 Computable Numbers and Functions. - 5 Rice s Theorem and the Recursion Theorem. - 6 Abstract Complexity Theory. - Solutions to Exercises. - Solutions for Chapter 1. - Solutions for Chapter 2. - Solutions for Chapter 3. - Solutions for Chapter 4. - Solutions for Chapter 5. - Solutions for Chapter 6. - References.
