The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility

Lempp, Steffen; Lerman, Manuel

J. Symbolic Logic, Tome 57 (1992) no. 1, p. 1120-1130 / Harvested from Project Euclid

Résumé

We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

Publié le : 1992-09-14
Classification:

@article{1183744061,
     author = {Lempp, Steffen and Lerman, Manuel},
     title = {The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility},
     journal = {J. Symbolic Logic},
     volume = {57},
     number = {1},
     year = {1992},
     pages = { 1120-1130},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744061}
}

Lempp, Steffen; Lerman, Manuel. The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility. J. Symbolic Logic, Tome 57 (1992) no. 1, pp.  1120-1130. http://gdmltest.u-ga.fr/item/1183744061/