Computability and Randomness in Dynamical Systems and Fractal Geometry

雷曼建议研究可计算性理论、动力系统和几何测度论之间的相互作用。Reimann打算使用动力系统和分形几何的概念来研究可计算性理论的结构，特别是最小图灵度的实数的集合Min。作为不可解度研究的中心对象，极小度最近在几何测度论方面表现出了有趣的性质。一个悬而未决的问题是Min的Hausdorff维度的确定。这个问题与随机性的提取、对角不可计算函数和Sack强迫有关。它还引发了关于REAL的算法独立性以及随机性(相对于任意度量)在拆分和连接下如何表现的问题。在第二个研究领域，Reimann建议从Borel等价关系的角度来研究算法的可约性。在描述集合论、遍历理论、拓扑动力学等领域的方法的显著融合中，研究人员成功地对许多等价关系进行了分类。然而，到目前为止，从可计算性理论归约中产生的大多数等价关系都抵制完全分类。Reimann打算研究LR等价，一种在有效随机性中具有基本重要性的等价关系，以及一致性在Borel等价关系分类中所起的作用。可计算性和随机性是推动20世纪科学革命并改变我们对世界的看法的两个基本思想。可计算性理论关注的是试图理解哪些问题是计算机可以解决的。它在20世纪30年代通过哥德尔、丘奇、图灵和其他人的工作发展成为一门严格的数学学科。大约在同一时间，科尔莫戈罗夫以测量理论概率的形式为随机性的概念提供了坚实的数学基础。有效随机性理论结合了概率论和可计算性理论，使得定性和定量地研究可计算性和随机性这两个概念相互界定和制约的方式成为可能。它给诸如“随机过程一定不可计算吗？”这样的问题赋予了精确的数学含义。或者“如果我们可以获得随机性，我们能促进计算吗？”拟议项目的主要目标是进一步研究随机性和可计算性之间的相互作用。在该项目的一个部分，将借助另外两个数学领域的概念-几何测度论和遍历理论来研究这种相互作用。在另一个部分，雷曼计划探索可计算性和随机性在动力系统的某些领域中所起的作用。后一个目标可以被视为一个长期项目的第一步--通过有效随机性理论，帮助为更好、更准确地理解世界上确实发生的随机性形式铺平道路。

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.