Annals of Pure and Applied Logic 170 (12):102716 (2019)
Abstract |
This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the k+1-r.e. numberings; all further reductions are obtained by concatenating these reductions.
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.1016/j.apal.2019.102716 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.Richard M. Friedberg - 1958 - Journal of Symbolic Logic 23 (3):309-316.
Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Π 1 0 Classes, L R Degrees and Turing Degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
Anti-Complex Sets and Reducibilities with Tiny Use.Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan & Guohua Wu - 2013 - Journal of Symbolic Logic 78 (4):1307-1327.
View all 8 references / Add more references
Citations of this work BETA
Rogers Semilattices of Limitwise Monotonic Numberings.Nikolay Bazhenov, Manat Mustafa & Zhansaya Tleuliyeva - 2022 - Mathematical Logic Quarterly 68 (2):213-226.
Similar books and articles
A Note on Partial Numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
Elementary Theories and Hereditary Undecidability for Semilattices of Numberings.Nikolay Bazhenov, Manat Mustafa & Mars Yamaleev - 2019 - Archive for Mathematical Logic 58 (3-4):485-500.
Strong Reducibility of Partial Numberings.Dieter Spreen - 2005 - Archive for Mathematical Logic 44 (2):209-217.
Friedberg Numberings in the Ershov Hierarchy.Serikzhan A. Badaev, Mustafa Manat & Andrea Sorbi - 2015 - Archive for Mathematical Logic 54 (1-2):59-73.
Some Independence Results for Control Structures in Complete Numberings.Sanjay Jain & Jochen Nessel - 2001 - Journal of Symbolic Logic 66 (1):357-382.
Some Independence Results for Control Structures in Complete Numberings.Sanjay Jain & Jochen Nessel - 2001 - Journal of Symbolic Logic 66 (1):357-382.
Topological Aspects of Numberings.Wolfram Menzel & Frank Stephan - 2003 - Mathematical Logic Quarterly 49 (2):129-149.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Stability of Representations of Effective Partial Algebras.Jens Blanck, Viggo Stoltenberg-Hansen & John V. Tucker - 2011 - Mathematical Logic Quarterly 57 (2):217-231.
Some Applications of Computable One-One Numberings.Martin Kummer - 1990 - Archive for Mathematical Logic 30 (4):219-230.
Reductions in the Theory of Types.K. Jaakko Hintikka - 1966 - Journal of Symbolic Logic 31 (4):660-660.
Review: K. Jaakko Hintikka, Reductions in the Theory of Types. [REVIEW]W. B. Pitt - 1966 - Journal of Symbolic Logic 31 (4):660-660.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Combinatory Reductions and Lambda Reductions Compared.Roger Hindley - 1976 - Mathematical Logic Quarterly 23 (7-12):1169-180.
Combinatory Reductions and Lambda Reductions Compared.Roger Hindley - 1977 - Mathematical Logic Quarterly 23 (7‐12):169-180.
Analytics
Added to PP index
2019-07-06
Total views
8 ( #1,010,831 of 2,520,788 )
Recent downloads (6 months)
1 ( #405,623 of 2,520,788 )
2019-07-06
Total views
8 ( #1,010,831 of 2,520,788 )
Recent downloads (6 months)
1 ( #405,623 of 2,520,788 )
How can I increase my downloads?
Downloads