Kenshi Miyabe

News
30 Oct 2025: Submitted to a journal, page created

Title
On the lower density of Solovay–Zheng–Rettinger degrees

Type
Research article

Publication
TBA

Abstract
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.

download
preprint

News
11 Oct 2025: New page
Oct 2025: Accepted

Title
Rate of convergence of computable predictions

Type
Research article

This is a journal version of the conference paper with the title Computable prediction.

Publication
To appear in Journal of Symbolic Logic
DOI: 10.1017/jsl.2025.10155

Abstract
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.

download
preprint

News
7 Nov 2023: submitted to a journal
13 Sep 2025: Published online

Title
Solovay reducibility via Lipschitz functions and signed-digit representation
Masahiro Kumabe, Kenshi Miyabe, and Toshio Suzuki

Type
Research article

Publication
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

Abstract
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.

download
preprint (23 May, 2024)
Read the paper on Meiji University Institutional Repository