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.

Readership

Undergraduates, graduate students, research mathematicians, and computer scientists and programmers interested in the general theory of computation.