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.
2009
9783642020162
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/389528