Solovay reducibility was introduced by Robert M. Solovay [6] in 1975 in terms of translation functions on rationals. It is a measure of relative approximation speed and thus also of relative randomness of reals. In the area of algorithmic randomness, Solovay reducibility has been intensively studied and several central results on left-c.e. reals have been obtained. Outside of the left-c.e. reals, Solovay reducibility is considered to be behaved badly [2]. 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 [9], and, recently, by Titov [7] and by Kumabe and co-authors [3, 4]. 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 [5] in 2022 and, independently, by Kumabe et al. [4] 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Variants of Solovay Reducibility

  • Ivan Titov

摘要

Solovay reducibility was introduced by Robert M. Solovay [6] in 1975 in terms of translation functions on rationals. It is a measure of relative approximation speed and thus also of relative randomness of reals. In the area of algorithmic randomness, Solovay reducibility has been intensively studied and several central results on left-c.e. reals have been obtained. Outside of the left-c.e. reals, Solovay reducibility is considered to be behaved badly [2]. 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 [9], and, recently, by Titov [7] and by Kumabe and co-authors [3, 4]. 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 [5] in 2022 and, independently, by Kumabe et al. [4] 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.