**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

Skip to content
# Kenshi Miyabe

## Posts

### Randomness of randomness deficiency

### Randomness notions in Muchnik and Medvedev degrees

### Coherence of reducibilities with randomness notions

### A way to judge using probability

### Using Almost-Everywhere Theorems from Analysis to Study Randomness

宮部賢志（ミヤベケンシ）

**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

**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

**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

**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

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