Index sets and universal numberings
From MaRDI portal
Publication:716308
DOI10.1016/J.JCSS.2010.07.001zbMath1251.03046OpenAlexW2100254722MaRDI QIDQ716308
Jason Teutsch, Sanjay Jain, Frank Stephan
Publication date: 28 April 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.07.001
Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28)
Related Items (4)
Effectivity questions for Kleene's recursion theorem ⋮ Enumerations including laconic enumerators ⋮ Things that can be made into themselves ⋮ On Approximate Decidability of Minimal Programs
Cites Work
- Unnamed Item
- Unnamed Item
- A guided tour of minimal indices and shortest descriptions
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. The theory of functions and sets of natural numbers.
- Extremes in the degrees of inferability
- On the Turing degrees of minimal index sets
- Kolmogorov complexity and the Recursion Theorem
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- A proof of Beigel's cardinality conjecture
- Frequency computations and the cardinality theorem
- Program size in restricted programming languages
- On the complexity of random strings
- A cardinality version of Beigel's nonspeedup theorem
- Post's Programme for the Ershov Hierarchy
- Enumerations of the Kolmogorov function
- Classes of Recursively Enumerable Sets and Degrees of Unsolvability
- Classes of Recursively Enumerable Sets and Their Decision Problems
- Theory and Applications of Models of Computation
- An introduction to Kolmogorov complexity and its applications
- Control structures in hypothesis spaces: The influence on learning
This page was built for publication: Index sets and universal numberings
