Computable Mathematics

在这个项目中，首席研究员将应用可计算性理论的方法来研究数学各个领域的有效内容和证明理论的力量。特别是，他将专注于可计算模型理论和代数、逆数学和组合原理的有效性，以及随机性和相对随机性的有效概念。在可计算模型理论中，该项目将继续开发方法，以解决由使模型理论概念有效而提出的问题。这些问题包括：使给定结构有效的不同方法之间的关系，使用较少模型的不同理论模型的有效程度之间的关系，以及在一般情况下可能出现的可计算性理论现象与在众所周知的结构类别中可能出现的可计算性理论现象之间的差异。赫希费尔特还将研究组合原理的可计算性理论和证明论方面，利用有效数学和反向数学程序之间的联系。最后，主要研究人员将在相对有效随机性的概念下研究(有效可逼近的)实数的结构，该概念通过使用初始分段的无前缀的Kolmogorov复杂性来定义。它是二十世纪初人们努力理解和形式化算法和可计算函数概念的自然结果。它既有纯粹的数学兴趣，也有基础兴趣，并与计算机科学有重要联系。这个项目旨在加深我们对结构如何影响可计算性，以及可计算性如何与现代数学的其他基本概念和数学基础(如随机性和证明理论强度)相互作用的理解。可计算性理论家发展了一种非常成功的关于数组的相对计算复杂性的理论，除了它内在的数学兴趣外，它在理论计算机科学中也产生了影响。这个项目的目标之一是继续发展一个新兴的相对算法随机性的并行理论，它可以作为一个理论框架来考虑这样的问题：我们应该在什么时候说一个无限集合比另一个集合更随机，以及集合的相对随机性对它们的相对计算复杂性有什么后果？

In this project the principal investigator will apply methodsfrom computability theory to study the effective content andproof-theoretic strength of various areas of mathematics. Inparticular, he will concentrate on computable model theory andalgebra, reverse mathematics and effectiveness of combinatorialprinciples, and effective notions of randomness and relativerandomness. In computable model theory, this project willcontinue the development of methods to address issues raised byeffectivizing model-theoretic notions. These issues include therelationships between the different ways that a given structuremay be effectivized, the relationships between the degree ofeffectivity of different models of theories with few models, andthe differences between the computability-theoretic phenomenathat can occur in general and those that can occur withinwell-known classes of structures. Hirschfeldt will also studycomputability-theoretic and proof-theoretic aspects ofcombinatorial principles, exploiting the connections betweeneffective mathematics and the reverse mathematicsprogram. Finally, the principal investigator will study thestructure of (effectively approximable) reals under notions ofrelative effective randomness defined through the use ofprefix-free Kolmogorov complexity of initial segments.The study of the effective content of mathematics has receivedincreasing attention in the last few decades. It is a naturaloutgrowth of the efforts to understand and formalize the notionsof algorithm and computable function undertaken in the early partof the twentieth century. It is of both pure mathematical andfoundational interest, and has important connections withcomputer science. This project aims to further our understandingof how structure affects computability, and how computabilityinteracts with other fundamental notions of modern mathematicsand foundations of mathematics, such as randomness andproof-theoretic strength. Computability theorists have developeda highly successful theory of relative computational complexityof sets of numbers, which, in addition to its intrinsicmathematical interest, has been influential in theoreticalcomputer science. One of the goals of this project is to continuethe development of an emerging parallel theory of relativealgorithmic randomness, which can act as a theoretical frameworkin which to consider questions such as: When should we say thatan infinite set is more random than another, and whatconsequences does the relative randomness of sets have for theirrelative computational complexity?