Computable Mathematics

可计算数学

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

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?

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