Computability and Randomness in Dynamical Systems and Fractal Geometry

Reimann建议研究可计算性理论、动力系统和几何测量理论之间的相互作用。Reimann打算用动力系统和分形几何的概念来研究可计算的理论结构，特别是最小图灵度实数的集合MIN。作为不可解度研究的中心对象，最小度最近在几何测量理论中表现出有趣的性质。一个悬而未决的问题是最小值的豪斯多夫维数的确定。这个问题涉及到抽取随机性、对角不可计算函数和Sacks强迫等问题。它还引发了关于实数的算法独立性的问题，以及在分割和连接下的有效随机性（相对于任意度量）如何表现。在第二个研究领域，Reimann建议从Borel等价关系的角度来研究算法的可约性。在描述集理论、遍历理论、拓扑动力学和其他领域的方法的显著融合中，研究人员成功地分类了许多等价关系。然而，大多数由可计算性理论可约性产生的等价关系迄今为止都无法完全分类。Reimann打算研究在有效随机性中具有重要意义的等价关系lr -等价，以及均匀性在Borel等价关系分类中的作用。可计算性和随机性是推动20世纪科学革命的两个基本思想，并改变了我们对世界的看法。可计算性理论关注的是试图理解哪些问题是计算机可以解决的。在20世纪30年代，通过Gödel、丘奇、图灵和其他人的工作，它发展成为一门严格的数学学科。大约在同一时期，Kolmogorov以测度论概率论的形式为随机性的概念提供了坚实的数学基础。有效随机性理论将概率论和可计算性理论结合起来，使定性和定量地研究可计算性和随机性这两个概念相互界定和制约的方式成为可能。它为诸如“随机过程一定是不可计算的吗？”或“如果我们能接触到随机性，我们能促进计算吗？”之类的问题提供了精确的数学意义。提出的项目的主要目标是进一步研究随机性和可计算性之间的相互作用。在项目的一部分，这种相互作用将在另外两个数学领域的概念的帮助下进行研究——几何测量理论和遍历理论。在另一部分，Reimann计划探索可计算性和随机性在动力系统某些领域的作用。后一个目标可以被看作是一个长期项目的第一步——通过有效随机性理论，帮助我们更好、更准确地理解随机性在这个世界中出现的形式。

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.