No label defined (Q4946105)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1421079
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1421079 |
Statements
3 December 2000
0 references
e-reducibility
0 references
jumps
0 references
high degrees
0 references
0.8606217503547668
0 references
0.8435167074203491
0 references
0.8379687070846558
0 references
0.8143166303634644
0 references
The paper concerns one of the now popular studies in Recursion Theory: reducibility by enumeration. Set \(A\) is e-reducible to set \(B\) if there exists a computably enumerable set \(\Phi\) such that \[ A=\{x: (\exists \text{ finite } D)[(x,D)\in \Phi \land D\subseteq B] \} \] where set \(D\) is identified with its canonical index. It is shown that the high e-degrees are exactly the \(\Sigma_2^0\) high e-degrees but not every \(\Sigma_2^0\) e-degree is high. For the entire collection see [Zbl 0923.00014].
0 references