A total Solovay reducibility and totalizing of the notion of speedability
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929429129723904 |
|---|---|
| author | Merkle, Wolfgang Titov, Ivan |
| author_facet | Merkle, Wolfgang Titov, Ivan |
| contents | While the set of Martin-Löf random left-c.e. reals is equal to the maximum degree of Solovay reducibility, Miyabe, Nies and Stephan(DOI:10.4115/jla.2018.10.3) have shown that the left-c.e. Schnorr random reals are not closed upwards under Solovay reducibility. Recall that for two left-c.e. reals~$α$ and~$β$, the former is Solovay reducible to the latter in case there is a partially computable function $φ$ and constant~$c$ such that for all rational numbers $q < β$ we have \[α- φ(q) < c(β- q).\] By requiring the translation function $φ$ to be total, we introduce a total version of Solovay reducibility that implies Schnorr reducibility. Accordingly, by Downey and Griffiths (DOI:10.2178/jsl/1082418542), the set of Schnorr random left-c.e. reals is closed upwards relative to total Solovay reducibility.
Furthermore, we observe that the notion of speedability introduced by Merkle and Titov (DOI:10.1007/978-3-030-50026-9_22) can be equivalently characterized via partial computable translation functions in a way that resembles Solovay reducibility. By requiring the translation function to be total, we obtain the concept of total speedability. Like for speedability, this notion does not depend on the choice of the speeding constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14869 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A total Solovay reducibility and totalizing of the notion of speedability Merkle, Wolfgang Titov, Ivan Logic 03D32 (Primary) 03D30, 68Q30 (Secondary) While the set of Martin-Löf random left-c.e. reals is equal to the maximum degree of Solovay reducibility, Miyabe, Nies and Stephan(DOI:10.4115/jla.2018.10.3) have shown that the left-c.e. Schnorr random reals are not closed upwards under Solovay reducibility. Recall that for two left-c.e. reals~$α$ and~$β$, the former is Solovay reducible to the latter in case there is a partially computable function $φ$ and constant~$c$ such that for all rational numbers $q < β$ we have \[α- φ(q) < c(β- q).\] By requiring the translation function $φ$ to be total, we introduce a total version of Solovay reducibility that implies Schnorr reducibility. Accordingly, by Downey and Griffiths (DOI:10.2178/jsl/1082418542), the set of Schnorr random left-c.e. reals is closed upwards relative to total Solovay reducibility. Furthermore, we observe that the notion of speedability introduced by Merkle and Titov (DOI:10.1007/978-3-030-50026-9_22) can be equivalently characterized via partial computable translation functions in a way that resembles Solovay reducibility. By requiring the translation function to be total, we obtain the concept of total speedability. Like for speedability, this notion does not depend on the choice of the speeding constant. |
| title | A total Solovay reducibility and totalizing of the notion of speedability |
| topic | Logic 03D32 (Primary) 03D30, 68Q30 (Secondary) |
| url | https://arxiv.org/abs/2407.14869 |