履歴
2024年11月4日ページ作成
タイトル
汎用的学習理論
種類
総説論文
ジャーナル
数理解析研究所講究録
RIMS共同研究(公開型)証明論と証明活動
2228 証明と計算の理論と応用
ダウンロード
京都大学リポジトリからダウンロード
Solovay reducibility via Lipschitz functions and signed-digit representation
履歴
2023年11月7日：投稿
タイトル
Solovay reducibility via Lipschitz functions and signed-digit representation
Masahiro Kumabe, Kenshi Miyabe, and Toshio Suzuki
種類
研究論文
出版情報
TBA
要旨
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.
Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension
履歴
2021年2月 アクセプト
2022年6月 出版
タイトル
Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension
Hiroyuki Imai, Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa, Toshio Suzuki
種類
査読ありの事後会議録
国際会議と雑誌
Computability Theory and Foundations of Mathematics
Proceedings of the 9th International Conference on Computability Theory and Foundations of Mathematics
The 9th International Conference on Computability Theory and Foundations of Mathematics, Wuhan, China, 21 – 27 March 2019
https://doi.org/10.1142/12917 | June 2022
Pages: 196
Edited By: NingNing Peng (Wuhan University of Technology, China), Kazuyuki Tanaka (Tohoku University, Japan), Yue Yang (National University of Singapore, Singapore), Guohua Wu (Nanyang Technological University, Singapore) and Liang Yu (Nanjing University, China)
要約
In our previous work, we characterized Solovay reducibility using Lipschitz condition,
and introduced quasi Solovay reducibility (qS-reducibility, for short) as a H ̈older condition counterpart.
In this paper, we investigate effective dimensions and ideals closely related to quasi Solovay reducibility by means of the rate of convergence.
We show that the qS-completeness among left-c.e. reals is equivalent to having a positive effective Hausdorff dimension.
The Solovay degrees of qS-complete left-c.e. reals form a filter. On the other hand, the Solovay degrees of non-qS-complete left-c.e. reals do not form an ideal.
Based on observations on the relationships between rational sequences and reducibility, we introduce a stronger version of qS-reducibility.
Given a degree of this reducibility, the lower cone (including the given degree) forms an ideal.
By developing these investigations, we characterize the effective dimensions by means of the rate of convergence.
We give a variation of the first incompleteness theorem based on Solovay reducibility.
ダウンロード
東京都立大学機関リポジトリで論文を読む
計算可能な予測
履歴
2019年7月 校正
タイトル
Computable prediction
種類
査読ありの会議録
国際会議と雑誌
Miyabe K. (2019) Computable Prediction. In: Hammer P., Agrawal P., Goertzel B., Iklé M. (eds) Artificial General Intelligence. AGI 2019. Lecture Notes in Computer Science, vol 11654. Springer, Cham
DOI https://doi.org/10.1007/978-3-030-27005-6_14
Abstract
We try to predict the next bit from a given finite binary string
when the sequence is sampled from a computable probability measure on the Cantor space.
There exists the best betting strategy among a class of effective ones up to a multiplicative constant,
the induced prediction from which is called algorithmic probability or universal induction by Solomonoff.
The prediction converges to the true induced measure for sufficiently random sequences.
However, the prediction is not computable.
We propose a framework to study the properties of computable predictions.
We prove that all sufficiently general computable predictions also converge to the true induced measure.
The class of sequences along which the prediction converges is related to computable randomness.
We also discuss the speed of the convergence.
We prove that, even when a computable prediction predicts a computable sequence,
the speed of the convergence cannot be bounded by a computable function monotonically decreasing to $0$.
一様相対化
履歴
2019年6月19日 オンライン
タイトル
Uniform relativization
種類
簡易査読ありの会議録，サーベイ
国際会議と雑誌
In: Manea F., Martin B., Paulusma D., Primiero G. (eds) Computing with Foresight and Industry. CiE 2019. Lecture Notes in Computer Science, vol 11558. Springer, Cham
DOI: https://doi.org/10.1007/978-3-030-22996-2_5
Abstract
This paper is a tutorial on uniform relativization. The usual relativization considers computation using an oracle, and the computation may not work for other oracles, which is similar to Turing reduction. The uniform relativization also considers computation using oracles, however, the computation should work for all oracles, which is similar to truth-table reduction. The distinction between these relativizations is important when we relativize randomness notions in algorithmic randomness, especially Schnorr randomness. For Martin-Löf randomness, its usual relativization and uniform relativization are the same so we do not need to care about this uniform relativization.
We focus on two specific examples of uniform relativization: van Lambalgen’s theorem and lowness. Van Lambalgen’s theorem holds for Schnorr randomness with the uniform relativization, but not with the usual relativization. Schnorr triviality is equivalent to lowness for Schnorr randomness with the uniform relativization, but not with the usual relativization. We also discuss some related known results.