Iterated relative recursive enumerability

DOI10.1007/BF01278463MaRDI QIDQ1344547zbMATH OpenOpenAlexFDO

Authors Peter G. Hinman, Peter A. Cholak

Publication date 20 April 1995

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01278463

zbMATH Keywords

\(m\)-REA degreeiterated hopsrecursively enumerable degreerecursively enumerable set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Review text

A result of Soare and Stob asserts that for any non-recursive r.e. set \(C\), there exists a r.e.\([C]\) set \(A\) such that \(A \oplus C\) is not of r.e. degree. A set \(Y\) is called [of] \(m\)-REA (\(m\)-REA\([C]\)) [degree] iff it is [Turing equivalent to] the result of applying \(m\)-many iterated `hops' to the empty set (to \(C\)), where a hop is any function of the form \(X \mapsto X \oplus W^ X_ e\). The cited result is the special case \(m = 0\), \(n = 1\) of our Theorem. For \(m = 0,1\), and any \((m + 1)\)-REA set \(C\), if \(C\) is not of \(m\)-REA degree, then for all \(n\) there exists an \(n\)-r.e.\([C]\) set \(A\) such that \(A \oplus C\) is not of \((m + n)\)-REA degree. We conjecture that this holds also for \(m \geq 2\).

Recommendations

• Extending properly n - REA sets1
• On the r. e. predecessors of d. r. e. degrees
• Relative enumerability in the difference hierarchy
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• On relative enumerability of Turing degrees

Cites work

• scientific article; zbMATH DE number 3809539 (Why is no real title available?)
• Pseudo Jump Operators. I: The R. E. Case
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers

Cited in

(6)

• Isolation in the CEA hierarchy
• Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting)
• scientific article; zbMATH DE number 4148069 (Why is no real title available?)
• Relative enumerability in the difference hierarchy
• Extending properly n - REA sets1
• Array nonrecursiveness and relative recursive enumerability

This page was built for publication: Iterated relative recursive enumerability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344547)