The natural embedding of the Turing degrees into the enumeration degrees preserves the jump operation, and maps isomorphically the computably enumerable Turing degrees onto the $Pi^0_1$ enumeration degrees. The embedding does not preserve minimal pairs, though, unless one of the two sides is low. In particular it is known that there exist high minimal pairs of c.e. Turing degrees that do not embed to minimal pairs of e-degrees. We show however that high minimal pairs of $Pi^0_1$ e-degrees do exist.
Sorbi, A., Wu, G., Yang, Y. (2009). High minimal pairs in the enumeration degrees. In Theory and Applications of Models of Computation (pp.335-344). Berlin : Springer [10.1007/978-3-642-02017-9_36].
High minimal pairs in the enumeration degrees
Sorbi, A.;
2009-01-01
Abstract
The natural embedding of the Turing degrees into the enumeration degrees preserves the jump operation, and maps isomorphically the computably enumerable Turing degrees onto the $Pi^0_1$ enumeration degrees. The embedding does not preserve minimal pairs, though, unless one of the two sides is low. In particular it is known that there exist high minimal pairs of c.e. Turing degrees that do not embed to minimal pairs of e-degrees. We show however that high minimal pairs of $Pi^0_1$ e-degrees do exist.File | Dimensione | Formato | |
---|---|---|---|
high-minimal.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
148.68 kB
Formato
Adobe PDF
|
148.68 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/389528