Computable functions

Shen and Vereshchagin base this text on lectures presented at the Moscow State U. Mathematics Dept., for which they select central notions and facts from the general theory of algorithms. Coverage includes computable functions, decidable and enumerable sets; universal functions and undecidability; numberings and operations; properties of G÷del numberings; fixed point theorem; m -reducibility and properties of enumerable sets; oracle computations; arithmetical hierarchy; Turing machines; arithmeticity of computable functions; and recursive functions. For undergraduate mathematics or computer science majors, mathematicians and programmers. Translated from Russian by V. N. Dubrovskii. Annotation c. Book News, Inc., Portland, OR (booknews.com)