On the reducibility of function classes

Abstract

N – the set of all natural numbers, F – the set of all total functions N→N, A, B<=F. We say that A is m-reducible to B (A<=m B), iff there is a recursive operator M such that f in A, iff M(f) in B for all f in F. Similarly, 1-reducibility, tt-, btt-, 1tt- and Turing reducibility can be introduced. Table of contents. 1. Introduction. 2. Definitions of reducibilities and their simplest properties. 3. m-reducibility and the arithmetical hierarchy. 4. m-reducibility on SIGMA_1^fn. 5. Special classes. 6. Comparing various reducibilities on SIGMA_1^fn. 7. Notes on reducibilities of classes of sets.