Computable Mathematics

在这个项目中，首席研究员将应用可计算性理论的方法来研究数学各个领域的有效内容和证明理论的强度。特别是，他将专注于可计算模型理论和代数，逆向数学和组合原理的有效性，以及随机性和相对随机性的有效概念。在可计算模型理论中，本项目将继续开发方法来解决由模型理论概念的有效化所引起的问题。这些问题包括一个给定结构可能被有效的不同方式之间的关系，具有少量模型的不同理论模型的有效性之间的关系，以及一般可能发生的可计算性理论现象与那些可能在已知的结构类别中发生的现象之间的差异。Hirschfeldt还将研究组合原理的可计算性理论和证明理论方面，利用有效数学和逆向数学程序之间的联系。最后，首席研究员将通过使用初始段的无前缀Kolmogorov复杂度来研究相对有效随机性概念下（有效近似）实数的结构。近几十年来，对数学有效内容的研究受到了越来越多的关注。这是20世纪早期对算法和可计算函数概念的理解和形式化的努力的自然结果。它既具有纯数学意义，又具有基础意义，并且与计算机科学有着重要的联系。该项目旨在进一步了解结构如何影响可计算性，以及可计算性如何与现代数学的其他基本概念和数学基础（如随机性和证明理论强度）相互作用。可计算性理论家已经发展了一个非常成功的关于数集的相对计算复杂性的理论，除了其固有的数学兴趣外，该理论在理论计算机科学中也很有影响力。这个项目的目标之一是继续发展一种新兴的相对算法随机性并行理论，它可以作为一个理论框架来考虑以下问题：我们什么时候应该说一个无限集比另一个集更随机，以及集合的相对随机性对它们的相对计算复杂性有什么影响？

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?