The mini-conference will take place in the CEMS School of Economic Sciences.
February 10. Location: Congo River Room (Tea Room on 2d floor)
- Cameron Freer, MIT.
Unique invariant measures, with an application to algorithmically random structures.
Given a countable structure, when is a presentation of it algorithmically random? Computable invariant measures concentrated on the isomorphism class of the structure provide one possible approach to this question, as suggested by Fouché and Nies (Logic Blog 2012). But when there are many such invariant measures, there may not be a single natural choice -- leading to the question of when there is a unique such invariant measure.
In joint work with Ackerman, Kwiatkowska, and Patel, we show that the isomorphism class of a countable structure in a countable language admits a unique
S\infty -invariant probability measure if and only if, for each n, it realizes a unique n-type up to permutation. Such a structure is called highly homogeneous; this notion arose in Cameron's 1976 classification of the reducts of the rational linear order. In particular, there are five such structures, up to interdefinability. Furthermore, we show that any countable structure admitting more than one invariant measure must admit continuum-many ergodic invariant measures.
15 min break
- Willem Fouché, Unisa.
Kolmogorov complexity and harmonic analysis.
Abstract. We use recent results (with S. Mukeru) on the Fourier analysis of the zero sets of Brownian motion to explore the diophantine properties of an algorithmically random Brownian motion ( also known as a complex oscillation). We discuss the construction and definability of perfect sets which are linearly independent over the rationals directly from Martin-L\ ¨of random reals. Finally we explore the recent work of Tsirelson on countable dense random sets to study the diophantine properties of local minimisers of Brownian motion.
 W. L. Fouche: Diophantine properties of Brownian motion: recursive aspects. To appear in the Festschrift on the occasion of Victor Selivanov's sixtieth birthday.
 W. L. Fouche and S. Mukeru: On the Fourier structure of the zero set of fractional Brownian motion, Statistics and Probability Letters 83 (2013), 459 - 466.
- Safari Mukeru, Unisa.
Stochastic integrals with respect to algorithmically random Brownian motion.
A function g defined on the unit interval is called complex oscillation if it can be uniformly approximated by a sequence of continuous piece-linear functions gn such that each gn is encoded by a binary string of high Kolmogorov-Chaitin complexity. The set of such functions has Wiener measure 1. They are fully characterised by infinite binary strings of high complexity.
We will discuss study stochastic integration from the point of view of complex oscillations. We prove that, under some computability properties on integrands, pathwise stochastic integrals exist for any complex oscillation. We prove also that Ito's lemma holds for each complex oscillation. Thus, constructing a continuous function satisfying Ito's lemma is reduced to constructing an infinite binary string of high Kolmogorov-Chaitin complexity.
15 min break
- Philipp Schlicht (Universitaet Bonn).
Infinite computations with random oracles .
We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? For Turing machines, the answer is yes by a classical theorem of Sacks. We show that the answer is independent from ZFC for ordinal time machines (OTMs) with and without ordinal parameters and give a positive answer for most other machines.
For instance, we consider infinite time Turing machines (ITTMs), unresetting and resetting infinite time register machines (wITRMs, ITRMs), and α-Turing machines (α-TMs) for countable admissible ordinals α. Randomness for infinite time machines is linked to randomness relative to notions from effective descriptive set theory. Work of Brattka, Miller and, Nies  connects randomness with differentiability and we are also interested in an analogous connections for infinite time randomness.
This is joint work with Merlin Carl .
 Merlin Carl and Philipp Schlicht: Infinite computations from random oracles, preprint
 Vasco Brattka, Joseph S. Miller and Andre Nies: Randomness and differentiability, preprint, 2011.
- Open Problems.
February 11, Seminar room on the first floor.
Welcome by Prof. Ilsa Basson, Chair of Department.
- Arno Pauly (Clare College, Cambridge University).
Point degree spectra of represented spaces.
It has long been known that any real number has a Turing degree. In 2004,
J. Miller proved that this fails to hold for the elements of the Hilbert
cube, and that the Medvedev degrees of points in the Hilbert cube form a
proper substructure of all the enumeration degrees.
We introduce the point
degree spectrum of a represented space as a substructure of the Medvedev
degrees. Various properties of spaces are connected to its
point degree spectrum. For instance, all points in a computable Polish space
have Turing degree iff the inductive dimension of the Polish space in the sense of topology exists.
about spaces depend on its degree structure having certain properties,
which subsequently gives rise to new questions in recursion theory.
This work is joint work with Takayuki Kihara.
15 min break
- Dieter Spreen (Universitaet Siegen).
The continuity problem in computability theory.
Computations are usually required to end in finite time. Because of this, only a finite amout of information about the input is used during the computation. Moreover, an output once written on the output tape cannot be changed anymore: given more information about the input, the machine can only extend what is already written on the output tape (monotonicity).
These properties not only hold for functions on the natural numbers, but also for the computation of operators on such functions. A natural topology can be defined on such spaces with respect to which computable operators turn out to be (effectively) continuous.
If one restricts one's interest to functions which are computable and which can therefore be presented by the programs computing them (or their codings), there is another way of defining the computability of operators: an operator is effective if it is tracked by a computable function on the code.
The continuity problem is the question whether effective operators are the restrictions (to computable inputs) of (effectively) continuous operators. Obviously, both approaches are rather unconnected. Nevertheless for certain important cases positive solutions were presented: In the case of operators on the partial computable functions this is due to Myhill and Shepherdson; in the case of the total computable functions to Kreisel, Lacombe and Shoenfield. In the first case the result has been generalised to certain types of directed-complete partial orders with the Scott topology (Constable-Egli; Smyth; Weihrauch; ...), in the other to separable metric spaces (Ceitin; Moschovakis). These two types of spaces are quite different, topologically. As follows from an example by Friedberg, effective operators are not continuous in general.
The situation remained unclear for quite a while. In 1984 Spreen and Young showed that for general topological T0 spaces, effective maps are effectively continuous if they have a witness for noninclusion. Later Spreen showed that this property is also necessary. It says that if the image of a basic open set under the operator is not included in a given basic open sets in its co-domain, then one needs be able to effectively produce a witness for that.
The condition seems natural when dealing with continuity. In the present talk we will give even more evidence for its canonicity. It will be shown that effective operators are always sequentially continuous, effectively. In classical topology it is well known that sequentially continuous maps are continuous. The proof can be transferred into a constructive framework. There is however one step in which in the classical proof the Axiom of Choice is used and the effective information that is needed here is exactly what is provided by the witness for noninclusion condition.
- André Nies (University of Auckland). Density randomness and analysis.
Abstract. A Martin-Loef random real is called 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, but not density random oracle computes every K-trivial.
I will survey work of others showing that this randomness notion is the same as left-c.e. martingale convergence along the binary expansion of the real. Using this, I characterized density randomness in terms of differentiability of the variation functions of computable functions (STACS 2014, to appear). Joint work with Kenshi Miyabe and Jing Zhang shows that density randomness is the same as being a Lebesgue point of each nonnegative lower semicomputable function with finite integral.
- Paul Potgieter (Unisa).
Salem sets and rapid points.
I shall discuss the rapid points of Brownian motion and of complex oscillations. In the case of Brownian motion, we know that such points have equal Hausdorff and Fourier dimension, thus forming a Salem set. For complex oscillations, only the Hausdorff dimension has been established, although it is strongly suspected that the Fourier dimension will be equal.
Prior to the ARA meeting, 10 of the participants were at a retreat at Intundla Lodge, Feb 5-9. See the report.