Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion

DOI10.2307/2274816zbMath0708.03020MaRDI QIDQ3489987

Robert M. Solovay, Carl G. jun. Jockusch, Robert I. Soare, Manuel Lerman

Publication date: 1989

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274816

zbMATH Keywords

fixed point; iterated jumps; generalization of the Arslanov completeness criterion

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

GENERALIZATIONS OF THE RECURSION THEOREM, Fixpoints and relative precompleteness, Lowness for isomorphism, countable ideals, and computable traceability, OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS, Randomness, relativization and Turing degrees, Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, Fractal dimension versus process complexity, Extending and interpreting Post's programme, On relative randomness, The noneffectivity of Arslanov's completeness criterion and related theorems, Ramsey-type graph coloring and diagonal non-computability, The d.r.e. degrees are not dense, \(\Sigma_ 5\)-completeness of index sets arising from the recursively enumerable Turing degrees, \(\Sigma_ 5\)-completeness of index sets arising from the lattice of recursively enumerable sets, Fixed-point selection functions, Precomplete numberings, Things that can be made into themselves, Fixed point theorems for precomplete numberings, On the Turing degrees of minimal index sets, Diagonally Non-Computable Functions and Bi-Immunity, A Survey of Mučnik and Medvedev Degrees, Three Theorems on n-REA Degrees: Proof-Readers and Verifiers, Calibrating Randomness, Ramsey's theorem and cone avoidance, Hyperarithmetical Index Sets in Recursion Theory