On the reducibility of function classes
Date
1972
Authors
Podnieks, Karlis
Journal Title
Journal ISSN
Volume Title
Publisher
Latvia State University
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.
Description
Copy of a paper published 1972 in Russian.
Keywords
recursive functions , reducibility , m-reducibility , tabular reducibility , Turing reducibility
Citation
Karlis Podnieks. On the reducibility of function classes. In: Equations of Mathematical Physics and Theory of Algorithms, Riga, Latvia State University, 1972, pp. 120–139 (in Russian, English translation: Automatic Control and Computer Sciences).