Computable Mathematics

在这个项目中，首席研究员将运用可计算性理论和逻辑学和理论计算机科学的其他分支的方法来研究数学各个领域的有效内容和证明理论的强度。特别是，他将专注于有效的随机性，可计算模型理论，反向数学和组合原理的有效性。他将研究实数的相对随机性，使用可计算性理论和算法信息论的方法，特别集中在k -平凡实数上，这是一个自然的实数类别，它远非随机，具有许多引人注目的性质和应用。在可计算模型理论中，他将继续发展方法来解决由模型理论概念的有效化所引起的问题，包括给定结构可能被有效化的不同方式之间的关系；模型少的情况下不同理论模型的有效性关系以及完全可决理论的特殊模型，如素数模型、齐次模型和饱和模型的度。他还将研究组合原理的可计算理论和证明理论方面，如拉姆齐定理的版本，以及与偏序和线性排序相关的原理，利用有效数学和反向数学程序之间的联系。近几十年来，对数学有效内容的研究越来越受到人们的关注。这是20世纪早期对算法和可计算函数概念的理解和形式化的努力的自然结果。它既具有纯数学意义，又具有基础意义，并且与计算机科学有着重要的联系。该项目旨在进一步了解结构如何影响可计算性，以及可计算性如何与现代数学的其他基本概念和数学基础（如随机性和证明理论强度）相互作用。可计算性理论家已经发展了一种非常成功的关于数集的相对计算复杂性的理论，除了它内在的数学兴趣外，它在理论计算机科学中也很有影响力。该项目的目标之一是继续发展一种新兴的相对算法随机性并行理论，它可以作为一个理论框架来考虑以下问题：我们什么时候应该说一个无限集比另一个集更随机，以及集合的相对随机性对它们的相对计算复杂性有什么影响？

In this project the principal investigator will apply methods fromcomputability theory and other branches of logic and theoretical computerscience to study the effective content and proof-theoretic strength ofvarious areas of mathematics. In particular, he will concentrate oneffective randomness, computable model theory, and reverse mathematics andeffectiveness of combinatorial principles. He will study the relativerandomness of reals, using methods from computability theory andalgorithmic information theory, concentrating in particular on theK-trivial reals, a natural class of reals that are far from random withwith many compelling properties and applications. In computable modeltheory, he will continue the development of methods to address issuesraised by effectivizing model-theoretic notions, including therelationships between the different ways that a given structure may beeffectivized; the relationships between the degree of effectivity ofdifferent models of theories with few models; and the degrees of specialmodels, such as prime, homogeneous, and saturated models, of completedecidable theories. He will also study computability-theoretic andproof-theoretic aspects of combinatorial principles such as versions ofRamsey's Theorem and principles related to partial and linear orderings,exploiting the connections between effective mathematics and the reversemathematics program.The study of the effective content of mathematics has received increasingattention in the last few decades. It is a natural outgrowth of theefforts to understand and formalize the notions of algorithm andcomputable function undertaken in the early part of the twentieth century.It is of both pure mathematical and foundational interest, and hasimportant connections with computer science. This project aims to furtherour understanding of how structure affects computability, and howcomputability interacts with other fundamental notions of modernmathematics and foundations of mathematics, such as randomness andproof-theoretic strength. Computability theorists have developed a highlysuccessful theory of relative computational complexity of sets of numbers,which, in addition to its intrinsic mathematical interest, has beeninfluential in theoretical computer science. One of the goals of thisproject is to continue the development of an emerging parallel theory ofrelative algorithmic randomness, which can act as a theoretical frameworkin which to consider questions such as: When should we say that aninfinite set is more random than another, and what consequences does therelative randomness of sets have for their relative computationalcomplexity?