We investigate completeness and universality notions, relative to different oracles, and the interconnection between these notions, with applications to arithmetical numberings. We prove that principal numberings are complete; completeness is independent of the oracle; the degree of any incomplete numbering is meet-reducible, uniformly complete numberings exist. We completely characterize which finite arithmetical families have a universal numbering.

Badaev, S., Goncharov, S., & Sorbi, A. (2003). Completeness and universality of arithmetical numberings. In S.B. Cooper, & S.S. Goncharov (a cura di), Computability and Models. Perspectives East and West (pp. 11-44). Dordrecht : Kluwer.

Completeness and universality of arithmetical numberings

SORBI, ANDREA
2003

Abstract

We investigate completeness and universality notions, relative to different oracles, and the interconnection between these notions, with applications to arithmetical numberings. We prove that principal numberings are complete; completeness is independent of the oracle; the degree of any incomplete numbering is meet-reducible, uniformly complete numberings exist. We completely characterize which finite arithmetical families have a universal numbering.
030647400X
Badaev, S., Goncharov, S., & Sorbi, A. (2003). Completeness and universality of arithmetical numberings. In S.B. Cooper, & S.S. Goncharov (a cura di), Computability and Models. Perspectives East and West (pp. 11-44). Dordrecht : Kluwer.
File in questo prodotto:
File Dimensione Formato  
completeness-universality-bgs.pdf

non disponibili

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 2.85 MB
Formato Adobe PDF
2.85 MB 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: http://hdl.handle.net/11365/423452