This page is only in Japanese
A Gap Phenomenon for Schnorr Randomness
News
20 Feb 2014, the slide file was uploaded
Title
A Gap Phenomenon for Schnorr Randomness
Type
CTFM
Download
miyabe-ctfm
Algorithmic randomness by philosophers
This page is only in Japanese.
Algorithmic information theory
This page is only in Japanese.
$L^1$-computability, layerwise computability and Solovay reducibility
News
17 July 2013, published
27 Mar 2013, accepted
19 Sep 2012, submitted
Title
L1-computability, layerwise computability and Solovay reducibility
Type
Full paper
Journal
Computability, 2:15-29, 2013.
Abstract
We propose a hierarchy of classes of functions that corresponds to the hierarchy of randomness notions. Each class of functions converges at the corresponding random points. We give various characterizations of the classes, that is, characterizations via integral tests, L1-computability and layerwise computability. Furthermore, the relation among these classes is formulated using Solovay reducibility for lower semicomputable functions.
Download
preprint
Correction
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.
This statement should be the following.
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that
$\{ r_0,r_1, … \}$ is dense in the interval $(0 , \infty)$ and $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.
This problem was pointed out by K. Weihrauch on 19 Jan 2014. I appreciate his notice.