Prior to the ARA meeting 11 of the participants were at a retreat in La Mothe, June 20-26. See the report.
Franklin, University of Connecticut (US).
Uniform-distribution randomness and genericity.
Abstract. Jeremy Avigad developed the concept of UD-randomness based on a theorem of Weyl on uniform distribution. Every Schnorr random real is UD-random, but not every UD-random is weakly 1-random (and vice versa), so this is a very weak randomness notion. I will discuss the relationship between the Turing degrees of UD-random reals and generic reals.
15 min break
- Laurent Bienvenu, Univ. Paris 7.
Recent progress on effective Brownian motion.
Abstract. This work is a contribution to the study of Martin-Löf randomness for Brownian motion, a line of study initiated by Asarin and Prokovsky in the 1980's, and continued by Kjos-Hanssen, Fouché and others in recent years. We study the zero sets of one-dimensional Martin-Löf random Brownian paths. It is well-known classically that with probability 1, the zero set of a Brownian path has dimension 1/2. It is not true however that the zero set of a Martin-Löf random Brownian path has constructive dimension 1/2 (indeed, it always has constructive dimension 1). We take a different approach and ask the question: for which reals t does there exists some Martin-Löf random path having t as a zero? We show that:
- There is no such real of constructive dimension < 1/2.
- All reals of constructive dimension > 1/2 have that property.
- Among reals of constructive dimension exactly 1/2, some have that property, some do not.
We also study the general structure of the zero set of a Martin-Löf random path and show in particular that the zero set of a random path B is a recursive closed set of reals relative to the oracle B. This has an elegant and surprising application to computable analysis, namely the following theorem: A computable instance of an n-dimensional Dirichlet problem always admits a computable solution.
This is joint work with Kelty Allen and Ted Slaman.
Kenshi Miyabe, Tokyo Daigaku.
L^1-computability and the computability of conditional probability.
I will present a hierarchy of variants of L^1-computability
that corresponds to the hierarchy of the notions of randomness.
This hierarchy also has a connection with differentiability
and the convergence of martingales.
As one application, I will give a sufficient condition
for van Lambalgen's theorem to hold for ML-randomness for non-uniform measures.
- Jason Rute, Carnegie-Mellon.
Transformations which preserve computable randomness.
Abstract. Preservation of randomness says that if x is random, and T is a computable map, then T(x) is random on the measure P_T (the distribution of T). Unlike Schnorr and Martin-Löf randomness, preservation of randomness does not hold for computable randomness (Bienvenu, Porter; Rute). However, one can get interesting partial results. My main result is that preservation of computable randomness holds for computable maps T such that the conditional expectation P[ | T] is computable. My main question is, are these the only computable maps which preserve computable randomness?
The proof of the main result uses computable analysis in interesting ways. I will give some review of conditional probability and of effectively measurable functions, as well as other applications of computable conditional probability to randomness.
15 min break
- Rupert Hölzl, Universitaet der Bundeswehr, Munich.
Algorithmic randomness and semimeasures .
Abstract. The topic of the ﬁeld of algorithmic randomness is to study what it means for an object to be
random. This is well-studied in the context of randomness relative to various kinds of probability
measures, both computable and non-computable. The general consensus in the ﬁeld is that
Martin-Löf randomness is the most natural randomness notion to consider here.
Much less well understood is randomness relative to semimeasures. Semimeasures can be seen
as defective measures, as they are not required to be additive: When looking at a set more and
more ﬁne-grainedly measure can be “lost” — that is, the sum of measures of a partition of a set
can be much smaller than the measure of that set as a whole. While this may at ﬁrst seem like an
artiﬁcial notion, it is in fact a very natural object to study in algorithmic randomness, as lower
semicomputable semimeasures are exactly the measures induced by Turing functionals.
In this talk, we will discuss some ongoing work on the problem of providing a natural and
useful deﬁnition of (Martin-Löf) randomness with respect to lower semicomputable semimeasures.
We ﬁrst agree on some desirable properties we expect from such a deﬁnition. Then by varying in
several ways the old deﬁnitions for randomness, we will generate a number of candidates for the
Joint with L. Bienvenu, C. Porter and P. Shafer
- Open Problems.
Greenberg, Victoria University of Wellington and Benoît
Monin, Université Paris 7.
Continuous Higher randomness. Part 1 by Greenberg. Part 2 by Monin.
Abstract. We survey recent results in the theory of higher randomness. We emphasize the role of continuous functions in the theory of randomness. This leads to finding the correct generalisation of Turing reducibility in the higher context, and thus to continuous relativisations of higher ML-randomness. However, some oracles misbehave, leading to the separation of notions which coincide in algorithmic randomness.
15 min break
- Joseph S. Miller (Univ. Wisconsin at Madison).
High(CR,MLR) and other properties close to PA.
An oracle X is High(CR, MLR) if every sequence that is computably
random relative to X is Martin-Löf random. It is not hard to show that
if X has PA degree, then it computes a martingale dominating an
optimal c.e. supermartingale, and hence X is High(CR, MLR). This was
observed by Franklin, Stephan and Yu, who then asked if High(CR, MLR) is
equivalent to PA. They showed that High(CR, MLR) has measure zero, and
that every element computes a Martin-Löf random sequence.
We investigate properties similar to High(CR, MLR). We show that some
are equivalent to PA, separate others from PA, but leave the
status of High(CR, MLR) open. We prove that if X computes a martingale
that dominates the optimal c.e. supermartingale (or even a fairly tame
universal martingale), then it has PA degree. On the other side, we
construct an X of non-PA degree such that every Pi^0_1 class of
positive measure contains a decidable Pi^0_1[X] class of positive
measure. (This property is implied by High(CR, MLR); the converse is
open.) We prove that such an X computes a K-bounded function of finite
weight, and that such a function computes an h-bounded DNC function
for any unbounded, non-decreasing, computable h.
This work is joint work with Greenberg and Nies.
- Chris Porter, Univ. Paris 7.
Demuth's work on Randomness and Analysis.
Abstract. I will survey Demuth's work on the connections between algorithmic randomness and constructive analysis. In particular, I will discuss Demuth's work on: (1) the relationship between randomness and differentiability; (2) Demuth's own notions of randomness (Demuth randomness and weak Demuth randomness); (3) connections between truth-table reducibility and certain reducibilities defined in terms of constructive analysis; and (4) the interactions of truth-table reducibility with randomness and semigenericity. This material is drawn from a survey for the BSL written jointly with André Nies and Antonín Kučera.
- Andre Nies, University of Auckland. Density randomness, martingale convergence, and differentiability.
Abstract. A ML-random real is density random if it satisfies the simplest effective version of the Lebesgue density theorem: every effectively closed set containing the real has density one at the real. The importance of this notion stems from the fact that each ML-random, not density random computes every K-trivial. I will survey work of others showing that this randomness notion is the same as left-c.e. martingale convergence, and my work characterizing it in terms of differentiability. I will also show that lowness for density randomness equals K-triviality. Finally I will consider the relationship with Oberwolfach randomness.
- Dan Turetsky, Kurt Goedel Center Vienna.
Weak 2-Randomness and Higher Dimensional Differentiability.
Abstract. Brattka, Miller and Nies investigated the relationship between algorithmic randomness and differentiability of effectively given functions. I will review some of their results and prove a higher dimensional analog of one of them.