### Muchnik degrees and Medvedev degrees of the randomness notions

2018年9月　受理
2018年3月11日　投稿

タイトル
Muchnik degrees and Medvedev degrees of the randomness notions

ALC2015とALC2017の共同議事録
World Scientificから出版予定

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.

ダウンロード
Muchnikdegrees

### Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm

2018年9月13日　スライドアップロード

タイトル
Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm

CTFM2018の講演

ダウンロード
CTFM-EFKP

### A tutorial in game-theoretic probability and algorithmic randomness

2018年9月13日　スライドアップロード

タイトル
A tutorial in game-theoretic probability and algorithmic randomness

CTFM2018の講演

ダウンロード
CTFM-tutorial

### Coherence of reducibilities with randomness notions

2017年2月1日　TOCS受理

タイトル
Coherence of reducibilities with randomness notions

Theory of Computing Systems – October 2018, Volume 62, Issue 7, pp 1599–1619
DOI: https://doi.org/10.1007/s00224-017-9752-2

Abstract
Loosely speaking, when $A$ is “more random” than $B$ and $B$ is “random”,
then $A$ should be random.
The theory of algorithmic randomness has some formulations of “random” sets
and “more random” sets.
In this paper, we study which pairs $(R,r)$ of randomness notions $R$
and reducibilities $r$ have the follwing property:
if $A$ is $r$-reducible to $B$ and $A$ is $R$-random,
then $B$ should be $R$-random.
The answer depends on the notions $R$ and $r$.
The implications hold for most pairs, but not for some.
We also give characterizations of $n$-randomness via complexity.

ダウンロード
preprint

### 重複対数の法則

2018年7月31日　スライドアップロード

タイトル

ダウンロード
LIL