Randomness in Recursion Theory and Effective Descriptive Set Theory

递归理论中的随机性和有效描述集合论

• 批准号: 0801270
• 负责人: Jan Reimann
• 金额: $ 5.91万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0801270&HistoricalAwards=false
• 关键词: Randomness; Recursion; Theory; Effective; Descriptive

In this project, the principal investigator proposes to study the relationship between algorithmic randomness and logical complexity with respect to the transfinite hierarchies of recursion theory and effective descriptive set theory. The strength of a randomness notion can be increased by allowing more complicated tests, where the complexity of a test is measured in terms of the aforementioned hierarchies. A basic result due to Reimann and Slaman established that for any natural number there are only countably many reals not random for any continuous probability measure. One goal of the project is to find a topological or measure-theoretic characterization of these countable sets. Furthermore, Reimann will try to extend the results obtained for arithmetical randomness to higher notions of randomness, i.e. to tests having access to projective parameters, proving co-countability and correlating it with large cardinals in set theory. An essential tool for realizing these objectives is the construction of a measure relative to which a given real is random. The project aims at finding new ways to do this, in particular it investigates how methods from measure theory and analysis can be used. Finally, the principal investigator will study the relation between randomness for probability measures and non-finite measures, most prominently Hausdorff measures. Previous results indicate an intriguing difference between the two concepts with respect to computability theoretic hierarchies.Randomness is a fundamental mathematical phenomenon whose understanding and investigation is one of the prime achievements of mathematics, and science in general, in the 20th century. Classical measure and probability theory do not allow for considering individual random objects, such as the outcome of a sequence (finite or infinite) of coin tosses. The theory of algorithmic randomness, as developed by Kolmogorov, Martin-Loef, Levin, and others, provides a uniform framework for defining such individual random content in a spectrum that spans from finite words to transfinite cardinals. It is inherent in our understanding of randomness that random objects should exhibit a rather high complexity, usually phrased as unpredictability or presence of chaos. Twentieth century logic, on the other hand, has put forth numerous hierarchies that capture the complexity of an object such as an infinite binary sequence with respect to its descriptive complexity, i.e. how hard it is to define or compute this object in a given mathematical theory such as first or second order arithmetic. Reimann's main goal is to studyhow logical complexity and randomness are intertwined. Previous research has shown that certain levels of logical complexity imply the presence of random content. The understanding of this relation, however, is far from complete. Among the principal questions Reimann tries to answer are: How is the the presence of randomness related to the definability strength of large cardinals? Are there other ways to capture the presence of random content within the hierarchies of logical complexity? Can in turn the logical complexity help to distinguish between randomness for different kinds of measures?

在这个项目中，主要研究者建议在递归理论和有效描述集理论的超有限层次上研究算法随机性和逻辑复杂性之间的关系。可以通过允许更复杂的测试来增加随机性概念的强度，其中测试的复杂性是根据上述层次结构来衡量的。Reimann和Slaman的一个基本结论是，对于任何自然数，对于任何连续概率测度，只有可数的实数不是随机的。该项目的一个目标是找到这些可数集的拓扑或测度理论表征。此外，Reimann将尝试将算术随机性的结果扩展到更高的随机性概念，即可以访问投影参数的测试，证明协可数性并将其与集合论中的大基数相关联。实现这些目标的一个重要工具是构建一个相对于给定实数是随机的度量。该项目旨在寻找新的方法来做到这一点，特别是它研究了如何使用测量理论和分析的方法。最后，首席研究员将研究概率测度的随机性与非有限测度（最突出的是Hausdorff测度）之间的关系。先前的结果表明，在可计算性理论层次方面，这两个概念之间存在有趣的差异。随机性是一种基本的数学现象，对它的理解和研究是20世纪数学乃至整个科学的主要成就之一。经典的测量和概率论不允许考虑单个随机对象，例如掷硬币序列（有限或无限）的结果。由Kolmogorov、Martin-Loef、Levin等人开发的算法随机性理论提供了一个统一的框架，用于定义从有限词到超有限基的频谱中的个体随机内容。我们对随机性的固有理解是，随机对象应该表现出相当高的复杂性，通常被描述为不可预测性或混乱的存在。另一方面，二十世纪的逻辑提出了许多层次结构，这些层次结构捕捉了一个对象的复杂性，比如一个无限二进制序列，相对于它的描述复杂性，即在给定的数学理论中定义或计算这个对象的难度，比如一阶或二阶算术。雷曼的主要目标是研究逻辑复杂性和随机性是如何交织在一起的。先前的研究表明，一定程度的逻辑复杂性意味着随机内容的存在。然而，对这种关系的理解还远远不够。Reimann试图回答的主要问题包括：随机性的存在与大基数的可定义性强度有何关系？是否有其他方法可以在逻辑复杂性的层次结构中捕获随机内容的存在？逻辑复杂性能否反过来帮助我们区分不同度量的随机性？