The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility (Q4032885)
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 150250
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility |
scientific article; zbMATH DE number 150250 |
Statements
The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility (English)
0 references
1 April 1993
0 references
Turing jump
0 references
embedding of finite partial orders
0 references
decidability
0 references
r.e. degrees
0 references
Turing reducibility
0 references
0 references
0.8542687892913818
0 references
0.8542687892913818
0 references
0.8086745738983154
0 references
0.7751418948173523
0 references
The paper shows the decidability of the existential theory of the r.e. degrees in the language of Turing reducibility and Turing reducibility of the jump. The authors express their expectation to extend the results to the language of Turing reducibility of all \(n\)th jumps shortly. The proof gives a direct embedding of arbitrary finite partial orders, controlling the reduction between their jumps at the same time.
0 references