Computable Mathematics

可计算数学

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

In this project the principal investigator will apply methods from computability theory and other branches of logic to study the effective content and proof-theoretic strength of various areas of mathematics. In particular, he will concentrate on algorithmic randomness, computable model theory, and reverse mathematics and effectiveness of combinatorial principles, computable structure theory (including computable algebra), and 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, other notions of computability theoretic lowness, and notions such as mutual information for infinite strings. He will also seek further applications of randomness to various areas of computability theory. In computable model theory, he will 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, measure theory, and other areas. 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?

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