David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 64 (3):927-945 (1999)
It is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions. This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes "having an enumeration with finite repetitions" is shown to be Σ 0 6 -complete
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Louise Hay (1969). Index Sets of Finite Classes of Recursively Enumerable Sets. Journal of Symbolic Logic 34 (1):39-44.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
Steffen Lempp & Theodore A. Slaman (1989). A Limit on Relative Genericity in the Recursively Enumerable Sets. Journal of Symbolic Logic 54 (2):376-395.
Dev K. Roy (1993). Recursive Versus Recursively Enumerable Binary Relations. Studia Logica 52 (4):587 - 593.
Iraj Kalantari & Allen Retzlaff (1979). Recursive Constructions in Topological Spaces. Journal of Symbolic Logic 44 (4):609-625.
Noam Greenberg (2005). The Role of True Finiteness in the Admissible Recursively Enumerable Degrees. Bulletin of Symbolic Logic 11 (3):398-410.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
Yuri Gurevich (1983). Decision Problem for Separated Distributive Lattices. Journal of Symbolic Logic 48 (1):193-196.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Added to index2009-01-28
Total downloads6 ( #211,419 of 1,099,863 )
Recent downloads (6 months)6 ( #51,330 of 1,099,863 )
How can I increase my downloads?