Computable Mathematics

可计算数学

• 批准号: 0500590
• 负责人: Denis Hirschfeldt
• 金额: $ 10.5万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-06-01 至 2008-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0500590&HistoricalAwards=false
• 关键词: Computable; Mathematics

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?

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