Author Archives: miyabe

Berry’s paradox

News
22 Apr, 2016. The slide file was uploaded

Title
Berry’s paradox

Type
Freshman seminar at math department of Meiji University

Download
Slide in Japanese

Posted in Talks | Leave a comment

Random numbers

News
22 Apr, 2016. The slide file was uploaded

Title
Random numbers

Type
A talk at a high school

Download
Slide (in Japanese)

Posted in Talks | Leave a comment

Can one compute a more random set uniformly?

News
24 Mar, 2016. The slide file was uploaded

Title
Can one compute a more random set uniformly?

Type
A talk at a meeting of Mathematical Society of Japan

Download
mathsoc

Posted in Talks | Leave a comment

An Introduction to statistics

News
24 Mar, 2016. The slide file was uploaded

Title
An Introduction to statistics

Type
A talk to junior-high students

Download
junior

Posted in Talks | Leave a comment

Randomness of randomness deficiency

News
26 Feb, 2016. The slide file was uploaded

Title
Randomness of randomness deficiency

Type
A talk in a seminar with Suzuki lab

Download
slide

Posted in Talks | Leave a comment

Randomness notions in Muchnik and Medvedev degrees

News
26 Feb, 2016. The slide file was uploaded

Title
Randomness notions in Muchnik and Medvedev degrees

Type
A talk in Dagstuhl seminar on “Computability Theory”

Download
slide

Posted in Talks | Leave a comment

Coherence of reducibilities with randomness notions

News
1 Feb 2016, accepted by TOCS

Title
Coherence of reducibilities with randomness notions

Type
Full paper

Journal
TOCS, post proceedings of CCR2016

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.

download
preprint

Posted in Publication | Leave a comment

A way to judge using probability

News
13 Dec, 2016 the slide file was uploaded

Title
A way to judge using probability

Type
A lecture in a high school

Download
slide in Japanese

Posted in Talks | Leave a comment

Using Almost-Everywhere Theorems from Analysis to Study Randomness

News
10 Oct 2016, published online
29 Feb 2016, Accepted by BSL
May 2015, Resubmitted.
3 Nov 2014. Submitted

Title
Using Almost-Everywhere Theorems from Analysis to Study Randomness
(with Jing Zhang and Andre Nies)

Type
Full paper

Journal
The Bulletin of Symbolic Logic, Volume 22, Issue 3
September 2016, pp. 305-331
arXiv
The latest version is here.

Abstract
We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin-Lo ̈f (ML) randomness. We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent.
(1) all effectively closed classes containing z have density 1 at z.
(2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z.
(3) z is a Lebesgue point of each lower semicomputable integrable function.
We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff’s pointwise ergodic theorem. Lastly we study randomness notions for density of $\Pi^0_n$ and $\Sigma^1_1$ classes.

Posted in Publication | Leave a comment

Randomness notions in Muchnik and Medvedev degrees

News
20 Sep, 2016, the slide file was uploaded

Title
Randomness notions in Muchnik and Medvedev degrees

Type
Talk at a meeting of CTFM2016

Download
abstract
slide

Posted in Talks | Leave a comment