カテゴリー: Publication

投稿日:

On the lower density of Solovay–Zheng–Rettinger degrees

履歴
2025年10月30日：雑誌に投稿，ページ作成

タイトル
On the lower density of Solovay–Zheng–Rettinger degrees

種類
研究論文

出版情報
TBA

要旨
In the theory of algorithmic randomness, it is well known that the Solovay degrees of left-c.e.\ reals are dense.
In this paper, we establish a corresponding lower density result for degrees of the modified version of Solovay reducibility introduced by Zheng and Rettinger.
It is known that the modified reducibility behaves better for computably approximable reals than the orignal reducibility. We call the modified one Solovay–Zheng–Rettinger reducibility (abbreviated as Solovay–ZR reducibility).
Our proof employs a completely different strategy from the known argument.
Furthermore, we demonstrate the existence of a quasi-minimal Solovay–ZR degree: a weakly computable real such that every left-c.e.\ real Solovay–ZR-reducible to it is necessarily computable.
Finally, we point out that this notion can be regarded as the dual counterpart to variation randomness.

ダウンロード
preprint

投稿日:

Rate of convergence of computable predictions

履歴
2025年10月11日：ページ作成
2025年10月：受理

タイトル
Rate of convergence of computable predictions

種類
研究論文

会議論文Computable predictionの雑誌版．

出版情報
To appear in Journal of Symbolic Logic
DOI: 10.1017/jsl.2025.10155

要旨
We consider the problem of predicting the next bit in an infinite binary sequence sampled from the Cantor space with an unknown computable measure.
We propose a new theoretical framework to investigate the properties of good computable predictions, focusing on such predictions’ convergence rate.

Since no computable prediction can be the best, we first define a better prediction as one that dominates the other measure.
We then prove that this is equivalent to the condition that the sum of the KL divergence errors of its predictions is smaller than that of the other prediction for more computable measures.
We call that such a computable prediction is more general than the other.

We further show that the sum of any sufficiently general prediction errors is a finite left-c.e. Martin-Löf random real.
This means the errors converge to zero more slowly than any computable function.

ダウンロード
preprint

投稿日:

Solovay reducibility via Lipschitz functions and signed-digit representation

履歴
2023年11月7日：投稿
2025年9月13日：オンライン

タイトル
Solovay reducibility via Lipschitz functions and signed-digit representation
Masahiro Kumabe, Kenshi Miyabe, and Toshio Suzuki

種類
研究論文

出版情報
Kumabe M, Miyabe K, Suzuki T.
Solovay reducibility via Lipschitz functions and signed-digit representation.
Computability. 2025;14(1):38-62.
doi:10.3233/COM-230486
https://journals.sagepub.com/doi/10.3233/COM-230486

要旨
We explore Solovay reducibility in the context of computably approximable reals, extending its natural characterization for left-c.e. reals via computable Lipschitz functions. Our paper offers two distinct characterizations: the first employs Lipschitz functions, while the second utilizes Turing reductions with bounded use with respect to signed-digit representation. Additionally, we examine multiple related reducibilities and establish separations among them. These results contribute to a refined perspective of the relationship between Solovay reducibility and computable Lipschitz functions.

ダウンロード
プレプリント(2024年5月23日版)
明治大学機関リポジトリで論文を読む