On the reducibility of function classes
| dc.contributor.author | Podnieks, Karlis | |
| dc.date.accessioned | 2017-04-18T06:06:23Z | |
| dc.date.available | 2017-04-18T06:06:23Z | |
| dc.date.issued | 1972 | |
| dc.description | Copy of a paper published 1972 in Russian. | en_US |
| dc.description.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. | en_US |
| dc.identifier.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). | en_US |
| dc.identifier.uri | https://dspace.lu.lv/dspace/handle/7/34959 | |
| dc.language.iso | rus | en_US |
| dc.publisher | Latvia State University | en_US |
| dc.relation.ispartof | Equations of Mathematical Physics and Theory of Algorithms | |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | recursive functions | en_US |
| dc.subject | reducibility | |
| dc.subject | m-reducibility | |
| dc.subject | tabular reducibility | |
| dc.subject | Turing reducibility | |
| dc.title | On the reducibility of function classes | en_US |
| dc.type | info:eu-repo/semantics/article | en_US |