Computable Functions

Based on the lectures for undergraduates at Moscow State University, this book presents a lively and concise introduction to the central facts and 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 complement the main text with over 150 problems. They 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 computer
scientists that would like to learn basics of the general theory of computation. The book is also an ideal reference source for designing a course.