ABSTRACT
Computable functions are the fundamental objects of recursion theory. E. L. Post introduced the notion of relative computability. Usually, degree theory is divided into global degree theory which studies the general properties of degrees, and local degree theory which studies properties of degrees below 0. In this chapter, the author considers hierarchies of sets and degrees based on the analysis of the complexity of recursive approximations of functions. The fundamental object of local degree theory is the notion of a recursively enumerable (r.e.) set, i.e. a set of integers whose members can be effectively listed. H. Putnam, E. M. Gold and Y. Ershov introduced a natural generalization of this property allowing the approximation to change more often.
