Category: Publication

News
Feb 2021, accepted to publication
June 2022, Published

Title
Rational sequences converging to left-c.e. reals of positive effective Hausdorff dimension

Hiroyuki Imai, Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa, Toshio Suzuki

Type
Post proceedings of a conference

Publication
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)

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

download
Read the paper on Tokyo Metropolitan University Institutional Repository

News
July 2019, Proof reading

Title
Computable prediction

Type
Conference paper

Publication
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$.

download
preprint
slide

News
May 4, 2018. Accepted by AOP

Title
Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales: a game-theoretic approach
(with T. Sasai and A. Takemura)

Type
Full paper

Journal
Annals of Probability,
Annals of Probability, Vol. 47, No. 2, 1136-1161, March 2019.

Abstract
We prove an Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales. Our proof is given in the framework of the game-theoretic probability of Shafer and Vovk. As many other game-theoretic proofs, our proof is self-contained and explicit.

download
arXiv

News
Sep 2018, accepted
11 Mar 2018, submitted to a Journal

Title
Muchnik degrees and Medvedev degrees of the randomness notions

Type
Research paper

Publication
The joint post-proceedings for ALC2015 and ALC2017 published via World Scientific

Proceedings of the 14th and 15th Asian Logic Conferences, pp. 108-128 (2019) January

Abstract
The main theme of this paper is computational power when a machine is allowed to access random sets.
The computability depends on the randomness notions and we compare them by Muchnik and Medvedev degrees.
The central question is whether, given an random oracle, one can compute a more random set.
The main result is that, for each Turing functional,
there exists a Schnorr random set whose output is not computably random.

download
Muchnikdegrees