The Degrees of Conditional Problems
Gao, Su
J. Symbolic Logic, Tome 59 (1994) no. 1, p. 166-181 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.
Publié le : 1994-03-14
Classification:  
@article{1183744442,
     author = {Gao, Su},
     title = {The Degrees of Conditional Problems},
     journal = {J. Symbolic Logic},
     volume = {59},
     number = {1},
     year = {1994},
     pages = { 166-181},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183744442}
}

Gao, Su. The Degrees of Conditional Problems. J. Symbolic Logic, Tome 59 (1994) no. 1, pp.  166-181. http://gdmltest.u-ga.fr/item/1183744442/