Iterated relative recursive enumerability (Q1344547): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Pseudo Jump Operators. I: The R. E. Case / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3657980 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf01278463 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2153470928 / rank | |||
Normal rank |
Latest revision as of 10:53, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Iterated relative recursive enumerability |
scientific article |
Statements
Iterated relative recursive enumerability (English)
0 references
20 April 1995
0 references
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\).
0 references
recursively enumerable set
0 references
recursively enumerable degree
0 references
iterated hops
0 references
\(m\)-REA degree
0 references