Computability and Randomness in Dynamical Systems and Fractal Geometry

动力系统和分形几何中的可计算性和随机性

• 批准号: 1201263
• 负责人: Jan Reimann
• 金额: $ 9.17万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1201263&HistoricalAwards=false
• 关键词: Computability; Randomness; Dynamical; Systems; Fractal

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.

Reimann建议研究可计算性理论、动力系统和几何测度理论之间的相互作用。Reimann打算使用动力系统和分形几何的概念来研究可计算性理论结构，特别是最小图灵度的实数集MIN。作为不可解度研究的一个中心对象，极小度最近在几何测度论中表现出了有趣的性质。一个开放的问题是确定的Hausdorff维数的最小值。这个问题涉及到有关提取的随机性，对角不可计算的功能，和萨克斯强迫的问题。它还激发了关于实数的算法独立性的问题，以及在分裂和连接下有效的随机性（相对于任意度量）如何表现。在第二个领域的调查，Reimann建议研究算法的可归约性的角度来看，博雷尔等价关系。从描述集合论、遍历理论、拓扑动力学和其他领域的方法的显著融合中，研究人员已经成功地对许多等价关系进行了分类。然而，大多数等价关系所产生的可计算性理论的可约性，迄今为止，抵制完整的分类。Reimann打算调查LR-等价，一个等价关系的基本重要性，在有效的随机性，也发挥作用的均匀性分类的博雷尔等价relations.Computability和随机性的分类是两个基本的想法，推动了科学革命的20世纪，改变了我们的方式思考世界。可计算性理论关注的是试图理解哪些问题可以用计算机解决。它是在20世纪30年代通过哥德尔、丘奇、图灵和其他人的工作发展起来的一门严格的数学学科。大约在同一时间，哥洛夫提供了概念的随机性与坚实的数学基础的形式措施理论的概率。有效随机性理论将概率论和可计算性理论结合在一起，使得定性和定量地研究可计算性和随机性这两个概念如何相互界定和制约成为可能。它给出了一个数学上精确的含义，如“随机过程必然不可计算吗？或者“如果我们有随机性，我们能促进计算吗？““建议的项目的主要目的是进一步研究随机性和可计算性之间的相互作用。在该项目的一部分，这种相互作用是研究的概念的帮助下，从其他两个领域的数学-几何测度理论和遍历理论。在另一部分中，Reimann计划探索可计算性和随机性在动力系统的某些领域中发挥的作用。后一个目标可以被看作是一个长期项目的第一步--通过有效随机性理论，为更好、更准确地理解随机性在这个世界上发生的形式铺平道路。