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-01-01
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.
| 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.
https://hdl.handle.net/11365/423452