Kenshi Miyabe

履歴
2025年5月23日アクセプト
2025年4月26日新しいプレプリントをアップロード
2024年12月26日ページ作成

タイトル
Real closed fields via strong Solovay reducibility
Masahiro Kumabe, Kenshi Miyabe, and Toshio Suzuki

種類
研究論文

ジャーナル
2025年5月23日Computabilityにてアクセプト
DOI: 10.1177/22113568251406825

ダウンロード
プレプリント
明治大学学術成果レポジトリで読む

履歴
2025年11月26日：ページ作成
2025年11月23日：受理
2025年7月20日：初稿投稿

タイトル
Randomness with respect to c.e. semimeasures

種類
研究論文

出版情報
Information and Computation
Special Issue in Memory of Vladimir V’yugin
Volume 307, November 2025, 105384
https://doi.org/10.1016/j.ic.2025.105384

要旨
We study algorithmic randomness with respect to c.e. semimeasures, which naturally arise as pushforward measures of partial computable mappings and therefore play a crucial role in algorithmic randomness.
We consider four distinct randomness notions: three based on complexity and one based on tests.
We systematically clarify their inclusion relationships.
Our main contribution is to construct concrete examples that separate these notions.
Furthermore, we investigate how they interact with the classical randomness preservation and no-randomness-from-nothing theorems, identifying precise conditions under which they continue to hold.

ダウンロード
semimeasure-elsarticle-20251126

履歴
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

履歴
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