About this Title
A. Shen, Independent University of Moscow, Moscow, Russia and N. K. Vereshchagin, Moscow State Lomonosov University, Moscow, Russia. Translated by Dr. V. N. Dubrovskii
Publication: The Student Mathematical Library
Publication Year 2003: Volume 19
ISBNs: 978-0-8218-2732-1 (print); 978-1-4704-2133-5 (online)
MathSciNet review: MR1946348
MSC: Primary 03-01; Secondary 03Dxx
This lively and concise book is based on the lectures for undergraduates given by the authors at the Moscow State University Mathematics Department and covers the basic notions of the general theory of computation. It begins with the definition of a computable function and an algorithm and discusses decidability, enumerability, universal functions, numberings and their properties, $m$-completeness, the fixed point theorem, arithmetical hierarchy, oracle computations, and degrees of unsolvability. The authors also cover specific computational models, such as Turing machines and recursive functions.
The intended audience includes undergraduate students majoring in mathematics or computer science, and all mathematicians and programmers who would like to learn the basics of the general theory of computation.
Undergraduates, graduate students, research mathematicians, and computer scientists and programmers interested in the general theory of computation.
Table of Contents
- Chapter 1. Computable functions, decidable and enumerable sets
- Chapter 2. Universal functions and undecidability
- Chapter 3. Numberings and operations
- Chapter 4. Properties of Gödel numberings
- Chapter 5. Fixed point theorem
- Chapter 6. $m$-reducibility and properties of enumerable sets
- Chapter 7. Oracle computations
- Chapter 8. Arithmetical hierarchy
- Chapter 9. Turing machines
- Chapter 10. Arithmeticity of computable functions
- Chapter 11. Recursive functions