8 Dec, 2018 The slide file was uploaded.
Construction of random and nonrandom sets
A talk in Sendai Logic School
Sep 2018, accepted
11 Mar 2018, submitted to a Journal
Muchnik degrees and Medvedev degrees of the randomness notions
The joint proceedings for ALC2015 and ALC2017 that will be published via World Scientific
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.
1 Feb 2016, accepted by TOCS
Coherence of reducibilities with randomness notions
Theory of Computing Systems – October 2018, Volume 62, Issue 7, pp 1599–1619
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.