Recursively enumerable sets and degrees

Keywords

Recursively enumerable language, Recursively enumerable set, Maximal set, Mathematics, Combinatorics

References

• Degrees of unsolvabilityJ. R. Shoenfield — 1971
• Boolean algebras, splitting theorems, and Δ^0_2 setsMichael Morley, Robert I. Soare — 1975
• Prioric games and minimal degrees below 0^(1)C Yates — 1974
• Undecidable and creative theoriesJ. R. Shoenfield — 1961
• Introduction to MetamathematicsHelena Rasiowa — 1952
• Review: U. L. Ersov, Decidability of the Elementary Theory of Relatively Complemented Distributive Lattices and of the Theory of FiltersF. Galvin — 1969
• Π⁰₁ classes and degrees of theoriesCarl G. Jockusch, Robert I. Soare — 1972
• On Group-Theoretic Decision Problems and Their Classification.Charles F. Miller — 1971
• Review: S. Tennenbaum, Degree of Unsolvability and the Rate of Growth of FunctionsFrank B. Cannonito — 1967
• -complete sets are not necessarily -completeA. H. Lachlan — 1975
• A lattice property of post's simple setPaul Frederick Cohen, Carl G. Jockusch — 1975
• Review: C. Spector, Inductively Defined Sets of Natural NumbersStephen J. Garland — 1969
• Deficiency sets and bounded information reducibilitiesLeonard P. Sasso — 1974
• Automorphisms of the lattice of recursively enumerable setsRobert I. Soare — 1974
• A simple set which is not effectively simpleGerald E. Sacks — 1964
• The Upper Semi-Lattice of Degrees of Recursive UnsolvabilityS. C. Kleene, Emil L. Post — 1954
• Distributive Initial Segments of the Degrees of UnsolvabilityA. H. Lachlan — 1968
• On the degrees of index sets. IIC. E. M. Yates — 1966
• Recursive enumerability and the jump operatorGerald E. Sacks — 1963
• Some theorems on classes of recursively enumerable setsJ. C. E. Dekker, John Myhill — 1958

Cited by

• Minimal Programs Are Almost OptimalCristian S. Calude, Hajime Ishihara, Takeshi Yamaguchi — 1999
• Computability and fractal dimensionJan Reimann — 2004
• Computability theory, reverse mathematics, and ordered fieldsOscar Levin — 2009
• Using Logic Programs to Reason about Infinite SetsDouglas Cenzer, Victor W. Marek, Jeffrey B. Remmel — 2004
• Computable Linear Orders and Turing ReductionsWhitney Patton Turner — 2012
• On relativized nondeterministic polynomial-time bounded computationsLi Xiang — 1985
• Dominance and Equivalence for Sensor-Based AgentsJason M. O’Kane, Steven M. LaValle — 2007
• Lowness Properties of Reals and RandomnessAndré Nies, André Nies — 2002
• An Effective Procedure for Computing "Uncomputable" FunctionsKurt Ammon — 2013
• The realizability approach to computable analysis and topologyAndrej Bauer, Dana Scott — 2000
• Separating the degree spectra of structuresTyler Markkanen — 2009
• Extremal problems on edge-colorings, independent sets, and cycle spectra of graphsKevin G. Milans — 2010
• Logical Approaches to Computational Barriers: CiE 2006Arnold Beckmann, Benedikt Löwe, D. Normann — 2007
• Reverse Mathematics and the Coloring Number of GraphsMatthew Jura — 2016
• Group Theoretic Properties of the Group of Computable Automorphisms of a Countable Dense Linear OrderSteffen Lempp, Charles McCoy, Andrey Morozov — 2002
• Small Π01 ClassesStephen Binns — 2006
• A sequentially computable function that is not effectively continuous at any pointPeter Hertling — 2006
• Combinatory algebras of functions and their modest setsC. Velzel — 2012
• Searching through the realsSam Sanders — 2015
• Nondeterminism fairness and a fundamental analogyEdith Spaan, Leen Torenvliet, Peter van Emde Boas — 1989

Related papers

• A Non-Splitting Theorem for d.r.e. SetsXiaoding Yi — 1996
• On sQ-completeness of recursively enumerable setsR. Sh. Omanadze — 1992
• The class of recursively enumerable subsets of a recursively enumerable setLouise Hay — 1973
• On recursive enumerability with finite repetitionsStephan Wehner — 1999
• Recursively enumerable generic setsWolfgang Maass — 1982
• Complexity properties of recursively enumerable sets andsQ-completenessR. Sh. Omanadze — 1997
• A New Proof of Smoryński’s TheoremApoloniusz Tyszka — 2017
• A New Proof of Smoryński’s TheoremApoloniusz Tyszka — 2017
• Universal diophantine equationJames P. Jones — 1982