ELC Workshop on Randomness andProbability Through Computability
Hongo Campus, The University of Tokyo, Japan
14 - 15 May 2013
Updated on May 13, 2013

Contents
1 General information

22 Participants

33 Programme

44 Abstracts
6
Osamu Watanabe. ELC Project Explanation For Deeper Understanding of the Limits of Computation . . . . . . . . 6
Shuji Kijima. Randomness in Algorithm Design . . . . . . . . 6
Rod Downey. Randomness from Borel through Turing andinto the 21st Century . . . . . . . . . . . . . . . . . . . . 6
Keita Yokoyama. A generalization of Levin-Schnorr’s theorem
7Toshio Suzuki. Forcing complexity . . . . . . . . . . . . . . . 7
Kenshi Miyabe. The preordering related to uniform Schnorr
randomness . . . . . . . . . . . . . . . . . . . . . . . . . 8
Kojiro Higuchi. Effective Strong Measure Zero . . . . . . . . . 9
NingNing Peng. Definability of Randomness via Another Randomness . . . . . . . . . . . . . . . . . . . . . . . . . . . 9André Nies. Differentiability and porosity . . . . . . . . . . . 9
Akimichi Takemura. An introduction to game-theoretic probability from statistical viewpoint. . . . . . . . . . . . . . 10
Bakhadyr Khoussainov. On finitely presented expansions of
semigroups, algebras, and groups. . . . . . . . . . . . . . 10
Rod Downey. Integer Valued Randomness. . . . . . . . . . . . 11
Takayuki Kihara. Bitwise addition and algorithmic randomness. 11
Toru Takisaka. On quantum Kolmogorov complexities andtheir relationships. . . . . . . . . . . . . . . . . . . . . . 111

1 General information
Title:
ELC Workshop on Randomness and Probability Through Computability
Date:
14 - 15 May 2013
Venue:
Room 367, 373 (Seminar Room A,D), No. 6 BLDG, Faculty of Engineering, Hongo Campus, The University of Tokyo, Japan
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)”,• “First, Aihara Innovative Mathematical Modelling Project”.

22 Participants
Invited speakers• Rod Downey (Victoria University of Wellington, New Zealand)• Bakhadyr Khoussainov (University of Auckland, New Zealand)• Shuji Kijima (Kyushu University, Japan)• André Nies (University of Auckland, New Zealand)

Other confirmed participants• Kojiro Higuchi (Chiba University, Japan)• Akitoshi Kawamura (University of Tokyo, Japan)• Takayuki Kihara (JAIST, Japan)• NingNing Peng (Tohoku University, Japan)• Toshio Suzuki (Tokyo Metropolitan University, Japan)• Akimichi Takemura (University of Tokyo, Japan)• Toru Takisaka (Kyoto University, Japan)• Kenshi Miyabe (University of Tokyo, Japan)• Osamu Watanabe (Tokyo Institute of Technology, Japan)• Keita Yokoyama (JAIST, Japan)33 Programme
Tuesday 14
Speaker 1. 13:10 – 13:30 Osamu Watanabe (Tokyo Institute of Technology, Japan)
ELC Project Explanation For Deeper Understanding of the Limits of Computation.
Speaker 2. 13:45 – 14:45 Shuji Kijima (Kyushu University, Japan)
Randomness in Algorithm Design.
Speaker 3. 15:00 – 15:45 Rod Downey (Victoria University of Wellington, New Zealand)
Randomness from Borel through Turing and into the 21st Century.
Speaker 4. 16:00 – 16:30 Keita Yokoyama (JAIST, Japan)
A generalization of Levin-Schnorr’s theorem.
Speaker 5. 16:45 – 17:15 Toshio Suzuki (Tokyo Metropolitan University, Japan)
Forcing complexity.
Speaker 6. 17:30 – 18:00 Kenshi Miyabe (University of Tokyo, Japan)
The preordering related to uniform Schnorr randomness.

Wednesday 15
Speaker 5. 9:30 – 10:00 Kojiro Higuchi (Chiba University, Japan)
Effective Strong Measure Zero.
Speaker 6. 10:15 – 10:45 NingNing Peng (Tohoku University, Japan)
Definability of Randomness via Another Randomness.
Speaker 7. 11:00 – 12:00 André Nies (University of Auckland, NewZealand)
Differentiability and porosity.

4

12:00 – 13:15 Lunch Break.
Speaker 8. 13:15 – 13:45 Akimichi Takemura (University of Tokyo,Japan)
An introduction to game-theoretic probability from statistical
viewpoint.
Speaker 9. 14:00 – 15:00 Bakhadyr Khoussainov (University of Auckland, New Zealand)On finitely presented expansions of semigroups, algebras, andgroups.
Speaker 10. 15:15 – 16:15 Rod Downey (Victoria University of Wellington, New Zealand)
Integer Valued Randomness.
Speaker 11. 16:30 – 17:00 Takayuki Kihara (JAIST, Japan)
Bitwise addition and algorithmic randomness.
Speaker 12. 17:15 – 17:45 Toru Takisaka (Kyoto University, Japan)
On quantum Kolmogorov complexities and their relationships.

5

4 Abstracts
ELC Project Explanation For Deeper
Understanding of the Limits of Computation.
Osamu Watanabe
Tokyo Institute of Technology, Japan.
Randomness in Algorithm DesignShuji Kijima.
Kyushu University, Japan.
”What is the property that a randomized algorithm really requires
for randomness?” Motivated by the question, this talk reviews some(randomized) algorithms which the speaker has been investigating. To
begin with, we are concerned with a fundamental problem finding frequent items in a data stream. For the problem, we have developed arandomized approximation algorithm using memory of only O(log log n)bits, presenting an efficient sampling algorithm in a stream, where ndenotes the length of the input stream which the algorithm does notknow in advance. Next, we briefly review the Markov chain Monte
Carlo (MCMC) method, which is a sophisticated and useful techniquefor random sampling. Finally, the speaker will talk about deterministic
random walks on finite graphs, motivated by a question if it is possible
to derandomize an MCMC.

Randomness from Borel through Turing and into
the 21st Century
Rod Downey.
Victoria University of Wellington, New Zealand.
This talk will be an overview of the basics of algorithmic randomness,hitting some of the high points. Additionally, we will look at some work

6

on Turing anticipating many of the ideas of Martin-Löf randomness, andnever published in his lifetime. This material concerns the numbertheortical concept of normality.

A generalization of Levin-Schnorr’s theorem
Keita Yokoyama.
JAIST, Japan.
A generalization of Levin-Schnorr’s theorem It is well-known, as
Levin-Schnorr s theorem, that Martin-Löf randomness and weak Chaitinrandomness coincide. In this talk, I will consider a generalized notionof randomness defined by a measure (a generalization of Martin-Lf randomness) and a generalized notion of randomness defined by a complexity function (a generalization of weak Chaitin randomness). Then,
I will show a version of Levin-Schnorr’s theorem to these notions.

Forcing complexity
Toshio Suzuki.
Tokyo Metropolitan University, Japan.
We overview our research on the minimum size of forcing conditions (cardinality of its domain) which force a given formula. We denote the minimum size by terminology “forcing complexity”. An infinite binary sequence of small forcing complexity is called a Dowd-type
generic set. This concept is different from the concept of resourcebounded genericity of Ambos-Spies et al., but this concept has connections with resource-bounded randomness and with computationalcomplexity. This is a joint work with M. Kumabe.

References[1] K. Ambos-Spies, E. Mayordomo, Resource-bounded measure andrandomness. In: Lecture Notes in Pure and Appl. Math., 187, 1–47
Dekker, 1997.

7

[2] K. Ambos-Spies, S. A. Terwijn, X. Zheng, Resource bounded randomness and weakly complete problems. Theoret. Comput. Sci.,
172 (1997) 195–207.
[3] M. Dowd, Generic oracles, uniform machines, and codes. Inf. Comput., 96 (1992) 65–76.
[4] M. Kumabe, T. Suzuki, Computable Dowd-type generic oracles.
In: Proc. 11th ALC (Singapore, 2009), 128–146, World Scientific,(2012).
[5] M. Kumabe, T. Suzuki, T. Yamazaki, Does truth-table of linear
norm reduce the one-query tautologies to a random oracle? Arch.
Math. Logic, 47 (2008) 159–180.
[6] T. Suzuki, Forcing complexity: minimum sizes of forcing conditions. Notre Dame J. Formal Logic, 42 (2001) 117–120.
[7] T. Suzuki, Degrees of Dowd-type generic oracles. Inf. Comput., 176(2002) 66–87.

The preordering related to uniform Schnorr
randomness
Kenshi Miyabe.
University of Tokyo, Japan.
One surprising result relating to Martin-Löf randomness is that lowness for Martin-Löf randomness is equivalent to K-triviality, which wasstrengthened to the equivalence of two reducibilities ≤LK and ≤LR byKjos-Hanssen et al. (2012). By considering uniform Schnorr randomness, Franklin and Stephan (2010) showed that lowness for uniform
Schnorr randomness is equivalent to Schnorr triviality. We strengthend
this result to the equivalence some reducibilities relating to uniform
Schnorr randomness.

8Effective Strong Measure Zero
Kojiro Higuchi.
Chiba University, Japan.
The strong measure zero is a concept for sets of reals which havebeen studied in the context of set theory. In the talk, we introduce
effectivizations of the concept. Sets of reals which satisfy one of theresulting concepts can be seen as sets of reals which are far from random. Using some methods developed in algorithmic randomness theory, we can characterize these effectivizations in terms of semimeasures,complexities and martingales. Furthermore, we obtain corresponding
characterizations of the strong measure zero by relativizing these characterizations to arbitrary real.

Definability of Randomness via Another
Randomness
NingNing Peng.
Tohoku University, Japan.
To compare two randomness notions with each other, we ask whether
a given randomness notion can be defined via another randomness notion. Inspired by Yu s pioneering study, we formalize our question using
the concept of relativization of randomness. We give some solutions to
our formalized questions. Our results also include the affirmative answer to the problem asked by Yu, i.e., whether Schnorr randomness
relative to the halting problem is equivalent to Martin-Löf randomness
relative to all low 1-generic reals.

Differentiability and porosity
André Nies.
University of Auckland, New Zealand.
Brattka, Miller and Nies proved in 2011 that a real z is computably
random iff every nondecreasing function is differentiable at z. I will9consider the analogous theorem when the effectiveness condition on thefunction is varied.
1. The analogous theorem holds for polynomial time randomness andpolynomial time computable nondecreasing functions.
2. For interval-c.e. function (essentially, the variation function of
a computable function), the right randomness strength is Martin-Loef
random reals at which the Lebesgue density theorem holds for effectively closed sets.
Surprisingly, the analytic notion of porosity plays a major role inboth proofs.

An introduction to game-theoretic probability
from statistical viewpoint.
Akimichi Takemura.
University of Tokyo, Japan.
We give an introduction to game-theoretic probability from the viewpoint of statistical testing. Game-theoretic probability by Shafer andVovk (2001) established a new foundation of probability theory by basing it on perfect information betting games. Kumon, Takemura and
Takeuchi have been contributing to this theory by studying the growthrate of capital processes in game-theoretic probability. A martingale in
the game-theoretic probability is the capital process in a betting game.
From statistical viewpoint it can also be understood as the likelihood
ratio process.

On finitely presented expansions of semigroups,algebras, and groups.
Bakhadyr Khoussainov.
University of Auckland, New Zealand.
Finitely presented algebraic systems are of foundational interest in
algebra, computability, and complexity. In this talk we will discuss10

finitely presented expansions of standard algebraic systems such as
semigroups, algebras and groups. The talk is based on the following
two papers:(1) Bakhadyr Khoussainov, Alexei Miasnikov. Finitely presented expansions of semigroups, groups, and algebras. Transactions of the AMS.
To appear.
(2) Denis Hirschfedlt, Bakhadyr Khoussainov. On finitely presented
expansions of semigroups. Algebra and Logic. Appeared in 2012.

Integer Valued Randomness.
Rod Downey.
Victoria University of Wellington, New Zealand. (with George
Barmpalias and Michael McInerney)
In 2012, Bienvenu, Stephan and Tuetsch began the study of an interesting notion of algorithmic randomness called integer valued randomness. This notion asks that we use martingales where the bets needto have discrete values. We will review the known results in this area,and look at recent material classifying the relationship of the randomness notion with the computably enumerable degrees, and notions ofgenericity.

Bitwise addition and algorithmic randomness.
Takayuki Kihara.
JAIST, Japan.
For infinite sequences x and y, the addition x + y is defined by (x +y)(n) = x(n) + y(n) mod 2. We show that x is low for uniform Kurtz
randomness if and only if x + y is Kurtz random whenever y is Kurtz
random.

On quantum Kolmogorov complexities and theirrelationships.

11Toru Takisaka.
Kyoto University, Japan.
In the early 2000s, several definitions of quantum Kolmogorov complexity (QKC) were proposed. QKC can be expected to be a useful
tool for analyzing quantum states (e.g. quantum entanglement) or tobe the foundation of the theory of ”quantum randomness”. Nevertheless, it seems for me that there is almost no progress in this area for thepast decade and a number of elementary facts are still not investigated.
I will introduce three definitions of QKC by Vitanyi / Gacs / Berthiaume et al. and relationships among them which are already known. Iwill also propose some conjectures now I am working on.

12