Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2410.15563 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913795947888640 |
|---|---|
| author | Titov, Ivan |
| author_facet | Titov, Ivan |
| contents | Outside of the left-c.e. reals, Solovay reducibility is considered to be behaved badly [10.1007/978-0-387-68441-3]. Proposals for variants of Solovay reducibility that are better suited for the investigation of arbitrary, not necessarily left-c.e. reals were made by Rettinger and Zheng [10.1007/978-3-540-27798-9_39], and, recently, by Titov [10.11588/heidok.00034250] and by Kumabe and co-authors [10.4115/jla.2020.12.2; 10.3233/COM-230486]. These variants all coincide with the original version of Solovay reducibility on the left-c.e. reals. Furthermore, they are all defined in terms of translation functions. The latter translate between computable approximations in the case of Rettinger and Zheng, are monotone in the case of Titov, and are functions between reals in the case of Kumabe et al.
In what follows, we derive new results on the mentioned variants and their relation to each other. In particular, we obtain that Solovay reducibility defined in terms of translation function on rationals implies Solovay reducibility defined in terms of translation functions on reals, and we show that the original version of Solovay reducibility is strictly weaker than its monotone variant.
Solovay reducibility and its variants mentioned so far have tight connections to Martin-Löf randomness, the strongest and most central notion of a random sequence. For the investigation of Schnorr randomness, total variants of Solovay reducibility have been introduced by Merkle and Titov [10.48550/arXiv.2407.14869] in 2022 and, independently, by Kumabe et al. [10.3233/COM-230486] in 2024, the latter again via real-valued translation functions. In what follows, we show that total Solovay reducibility defined in terms of rational functions implies total Solovay reducibility defined in terms of real functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_15563 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Variants of Solovay reducibility Titov, Ivan Logic Information Theory Logic in Computer Science 03D32 (Primary) 03D30, 68Q30 (Secondary) Outside of the left-c.e. reals, Solovay reducibility is considered to be behaved badly [10.1007/978-0-387-68441-3]. Proposals for variants of Solovay reducibility that are better suited for the investigation of arbitrary, not necessarily left-c.e. reals were made by Rettinger and Zheng [10.1007/978-3-540-27798-9_39], and, recently, by Titov [10.11588/heidok.00034250] and by Kumabe and co-authors [10.4115/jla.2020.12.2; 10.3233/COM-230486]. These variants all coincide with the original version of Solovay reducibility on the left-c.e. reals. Furthermore, they are all defined in terms of translation functions. The latter translate between computable approximations in the case of Rettinger and Zheng, are monotone in the case of Titov, and are functions between reals in the case of Kumabe et al. In what follows, we derive new results on the mentioned variants and their relation to each other. In particular, we obtain that Solovay reducibility defined in terms of translation function on rationals implies Solovay reducibility defined in terms of translation functions on reals, and we show that the original version of Solovay reducibility is strictly weaker than its monotone variant. Solovay reducibility and its variants mentioned so far have tight connections to Martin-Löf randomness, the strongest and most central notion of a random sequence. For the investigation of Schnorr randomness, total variants of Solovay reducibility have been introduced by Merkle and Titov [10.48550/arXiv.2407.14869] in 2022 and, independently, by Kumabe et al. [10.3233/COM-230486] in 2024, the latter again via real-valued translation functions. In what follows, we show that total Solovay reducibility defined in terms of rational functions implies total Solovay reducibility defined in terms of real functions. |
| title | Variants of Solovay reducibility |
| topic | Logic Information Theory Logic in Computer Science 03D32 (Primary) 03D30, 68Q30 (Secondary) |
| url | https://arxiv.org/abs/2410.15563 |