Computable Mathematics

可计算数学

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

In this project the principal investigator will apply methods from computability theory and other branches of logic and theoretical computer science to study the effective content and proof-theoretic strength of various areas of mathematics. In particular, he will concentrate on effective randomness, computable model theory, and reverse mathematics and effectiveness of combinatorial principles, with a particular emphasis on the connections between these areas.Among other areas in the theory of randomness, he will study properties of ``far from random'' sets and the connections between them and notions of mutual information for infinite strings. He will also seek further applications of randomness to various areas of computability theory. In computable model theory, he wl continue to address issues raised by effectivizing model theoretic notions, including the relationships between the degree of effectivity of different models of theories with few models and the computability theoretic and proof theoretic aspects of special models, such as prime, homogeneous, and saturated models. He will also further investigate computability theoretic and proof theoretic aspects of combinatorial principles as well as principles arising from model theory. In this work he will exploit the connections between effective mathematics and the reverse mathematics program, which aims to calibrate the strength of theorems of ordinary mathematics in terms of the (set existence and induction) axioms needed to prove them.The study of the effective content of mathematics has received increasing attention in the last few decades. It is a natural outgrowth of the efforts to understand and formalize the notions of algorithm and computable function undertaken in the early part of the twentieth century. It is of both pure mathematical and foundational interest, and has important connections with computer science. This project aims to further our understanding of how structure affects computability, and how computability interacts with other fundamental notions of modern mathematics and foundations of mathematics, such as randomness and proof-theoretic strength. Computability theorists have developed a highly successful theory of relative computational complexity of sets of numbers, which, in addition to its intrinsic mathematical interest, has been influential in theoretical computer science. One of the goals of this project is to continue the development of an emerging parallel theory of relative algorithmic randomness, which can act as a theoretical framework in which to consider questions such as: When should we say that an infinite set is more random than another, and what consequences does the relative randomness of sets have for their relative computational complexity?

在这个项目中，首席研究员将应用可计算性理论以及逻辑和理论计算机科学的其他分支的方法来研究数学各个领域的有效内容和证明理论的力量。特别是，他将专注于有效随机性、可计算模型理论、逆数学和组合原理的有效性，特别强调这些领域之间的联系。在随机性理论的其他领域中，他将研究“远离随机”集合的性质以及它们与无限字符串的互信息概念之间的联系。他还将寻求随机性在可计算性理论的各个领域的进一步应用。在可计算模型理论中，他将继续讨论模型理论概念的有效性问题，包括模型较少的不同理论模型的有效性程度与特殊模型的可计算性理论和证明论方面的关系，如素数模型、齐次模型和饱和模型。他还将进一步研究组合原理的可计算性理论和证明理论方面，以及源于模型理论的原理。在这项工作中，他将探索有效数学和反向数学程序之间的联系，该程序旨在根据证明普通数学定理所需的(集合存在和归纳法)公理来校准它们的强度。在过去的几十年里，对数学有效内容的研究越来越受到关注。它是二十世纪初人们努力理解和形式化算法和可计算函数概念的自然结果。它既有纯粹的数学兴趣，也有基础兴趣，并与计算机科学有重要联系。这个项目旨在加深我们对结构如何影响可计算性，以及可计算性如何与现代数学的其他基本概念和数学基础(如随机性和证明论强度)相互作用的理解。可计算性理论家发展了一个非常成功的关于数组的相对计算复杂性的理论，除了它内在的数学兴趣之外，它在理论计算机科学中也产生了影响。这个项目的目标之一是继续发展一个新兴的相对算法随机性的并行理论，它可以作为一个理论框架来考虑这样的问题：我们应该在什么时候说一个无限集合比另一个集合更随机，以及集合的相对随机性对它们的相对计算复杂性有什么影响？