Computability and Randomness in Dynamical Systems and Fractal Geometry

Reimann proposes to investigate interactions between computability theory, dynamical systems, and geometric measure theory. Reimann intends to use concepts from dynamical systems and fractal geometry to study computability theoretic structures, in particular, the set MIN of reals of minimal Turing degree. Being a central object in the study of degrees of unsolvability, minimal degrees have recently exhibited interesting properties with respect to geometric measure theory. An open problem is the determination of the Hausdorff dimension of MIN. This problem is related to questions concerning extraction of randomness, diagonally non-computable functions, and Sacks forcing. It also motivates questions about algorithmic independence of reals, and how effective randomness (with respect to arbitrary measures) behaves under splits and joins. In a second area of investigation, Reimann proposes to study algorithmic reducibilities from the point of view of Borel equivalence relations. In a remarkable confluence of methods from descriptive set theory, ergodic theory, topological dynamics, and other areas, researchers have successfully classified many equivalence relations. Yet most equivalence relations arising from computability theoretic reducibilities have so far resisted complete classification. Reimann intends to investigate LR-equivalence, an equivalence relation of fundamental importance in effective randomness, and also the role uniformity plays in the classification of Borel equivalence relations.

Computability and randomness are two of the fundamental ideas that drove the scientific revolutions of the 20th century and changed the way we think about the world. Computability theory concerns itself with trying to understand which problems are solvable by computers. It was developed as a rigorous mathematical discipline in the 1930s through the work of Gödel, Church, Turing and others. Around the same time, Kolmogorov provided the notion of randomness with a solid mathematical foundation in the form of measure theoretic probability. The theory of effective randomness, which brings together probability theory and computability theory, has made it possible to qualitatively and quantitatively study the ways in which the two notions, computability and randomness, delimit and condition each other. It gives a mathematically precise meaning to questions like 'Are random processes necessarily uncomputable?' or 'If we have access to randomness, can we facilitate computation?' The major objective of the proposed project is to further the study of the interaction between randomness and computability. In one part of the project, this interaction is to be studied with the help of concepts from two other areas of mathematics - geometric measure theory and ergodic theory. In another part, Reimann plans to explore the role computability and randomness play in certain areas of dynamical systems. The latter objective can be seen as a first step of a long-term project - to help pave the way for a better, more exact understanding of the forms in which randomness does occur in this world, through the theory of effective randomness.