Randomness in Recursion Theory and Effective Descriptive Set Theory

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

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?