Lectures on mathematical logic and theory of algorithms. Part 3. Calculated functions. 5th edition, stereotypical. Vereshchagin N.K., Shen A.

The book was written based on the materials of lectures and seminars held by authors for younger students of Mehmat. Moscow State University. It tells about the basic concepts of the general theory of computable functions (computability, permissibility, enumeration, universal functions, numbering and their properties, TP-completeness, a fixed point, arithmetic hierarchy, calculations with an oracle, degree of insoluble) and specific computing models ( Turing machines, recursive functions). The presentation is designed for students of mathematical schools, mathematicians and all those interested in the basics of the theory of algorithms. The book contains about 100 tasks of various difficulties.

The previous edition of the book was published in 2012