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, 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