ELC Seminar on Algorithmic
Randomness
Hongo Campus, The University of Tokyo, Japan
13 - 14 May 2013
Updated on May 8, 2013.

Contents
1 General information

22 Programme

33 Abstracts
Takayuki Kihara. Lowness for randomness and set theory of
the real line. . . . . . . . . . . . . . . . . . . . . . . . . .
Kenshi Miyabe. Uniform relativization and almost uniformrelativization. . . . . . . . . . . . . . . . . . . . . . . . .
Akitoshi Kawamura. Polynomial-time randomness and differentiability. . . . . . . . . . . . . . . . . . . . . . . . . . .

4

144
6

1 General information
Title:ELC Seminar on Algorithmic Randomness
Date:
13 - 14 May 2013
Venue:
237 Chemistry Building, Hongo Campus, The University of Tokyo,
Japan.
Enter Science Building 7, go up one floor and then through the connecting corridor.
The details are on the website.
Local Organizers:
Akitoshi Kawamura (kawamura@is.s.u-tokyo.ac.jp),
Kenshi Miyabe (research@kenshi.miyabe.name)
This workshop is jointly sponsored by“Exploring the Limits of Computation (ELC)”
and“First, Aihara Innovative Mathematical Modelling Project”.

22 Programme
Monday 13
Speaker 1. 9:30 – 12:30 Takayuki Kihara (JAIST, Japan)
Lowness for randomness and set theory of the real line.
12:30 – 14:00 Lunch Break.
Speaker 2. 14:00 – 17:00 Kenshi Miyabe (University of Tokyo, Japan)
Uniform relativization and almost uniform relativization.

Tuesday 14
Speaker 3. 10:00 – 11:30 Akitoshi Kawamura (University of Tokyo,Japan)
Polynomial-time randomness and differentiability.

33 Abstracts
Lowness for randomness and set theory of the realline.
Takayuki Kihara
JAIST, Japan.
If an infinite binary sequence is captured by a small subset of Cantor space, it shall be considered as far from being random. Roughlyspeaking, an infinite binary sequence is said to be “effectively” random
if it is not captured by a null set with an “effective” Borel code. In theabove definition, the word “null” shall be able to be replaced with any
ideal in Cantor space. With this line, many researchers in algorithmic
randomness theory have studied the notion of effective dimension: aninfinite binary sequence is effective Hausdorff dimension ≤ d if for everye > d, it is captured by an He -null set with a “effective” Borel code,
where He denotes the e-dimensional Hausdorff measure.
In set theory, there is a depthful study on σ-ideals in Cantor space.
Among them are the strong measure zero sets SN , the meager-additive
sets M+ , and the null-additive sets N +. As proved by Laver in 1976,(under the consistency of ZFC) there is a model of ZFC with no uncountable set in SN (hence, in M+ and N +). Nevertheless we will
see that their effective versions produce fruitful results on algorithmicrandomness. More precisely, we characterize lowness for randomness byusing the effective versions of these σ-ideals, and we justify the belief
that the concept of Kolmogoriv complexity is a tool to estimate howdifficult it is to capture an infinite sequence in a small set.

Uniform relativization and almost uniformrelativization.
Kenshi Miyabe.
University of Tokyo, Japan.
The topic of this talk is van Lambalgen’s theorem, which says thatA⊕B is Martin-Löf random if and only if A is Martin-Löf random and B

4

is Martin-Löf random relative to B [4]. Such a theorem should hold for
all natural randomness notions. Although some researchers found thatvan Lambalgen’s theorem does not hold for some randomness notions,this is because the relativization is not appropriate.
In the first part, we review such motivation of introducing uniform
relativization and show that van Lambalgen’s theorem holds for uniform Schnorr randomness and uniformly computable randomness (in aweaker sense). This part is mainly from Miyabe [2] and Miyabe andRute [3].
In the second part, we study van Lambalgen’s theorem for uniform
Kurtz randomness. A little unexpectedly, van Lambalgen’s theorem
does not hold for uniform Kurtz randomness. This part is from Kiharaand Miyabe [1].
In the last part, we introduce another relativization, which we callalmost uniform relativization. Actually we can show that van Lambalgen’s theorem holds for almost uniform weak n-randomness for alln ≥ 1. I also raise some questions relating to this problem.

References[1] T. Kihara and K. Miyabe. Uniform Kurtz randomness. In preparation.
[2] K. Miyabe. Truth-table Schnorr randomness and truth-table reducible randomness. Mathematical Logic Quarterly, 57(3):323–338,2011.
[3] K. Miyabe and J. Rute. Van Lambalgen’s Theorem for uniformly
relative Schnorr and computable randomness. To appear in Proceedings of the Twelfth Asian Logic Conference.
[4] M. van Lambalgen. Random sequences. PhD thesis, University ofAmsterdam, 1987.

5

Polynomial-time randomness and differentiability.
Akitoshi Kawamura.
University of Tokyo, Japan.
The Brattka-Miller-Nies Theorem states that a real number is computably random if and only if every nondecreasing computable realfunction is differentiable at it. The proof is more involved than thissimple statement might suggest, because we need to bridge between infinite sequences and the real numbers they represent, essentially proving
the base invariance of randomness. In this talk I will look closely into
this argument and discuss the polynomial-time (and other complexity)
versions of the theorem and related statements. (Ongoing work withKenshi Miyabe.)6