FRG: Collaborative Research: Computability-Theoretic Aspects of Combinatorics

FRG：协作研究：组合学的可计算性理论方面

基本信息

批准号：
1854355
负责人：
Damir Dzhafarov
金额：
$ 37.95万
依托单位：
University of Connecticut
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854355&HistoricalAwards=false
关键词：
FRG Collaborative Research Computability Theoretic

项目摘要

Computability theory arose out of the development by Turing and others of a mathematically precise definition of the notion of algorithm. One of the most fruitful developments in this field has been the study of the algorithmic content of mathematics. At the same time, concerns about the foundations of mathematics have led to the analysis of different formal systems for mathematical reasoning, and the study of the relative power of such systems. The computability-theoretic approach has turned out to play a key role in this project. Combinatorics is an area of mathematics whose methods and results underlie a great deal of mathematical reasoning, so the study of its algorithmic content and of the systems required to formalize its methods is particularly important. Computable combinatorics has a long history, but has seen a recent surge of interest highlighting the fact that computability-theoretically natural notions tend to be combinatorially natural, and vice-versa. This project aims to strengthen the connections between computability theory and combinatorics by increasing our understanding of the algorithmic content of combinatorial principles, through a concerted group effort to use what we have learned in recent years to systematize the area further, work toward solving a number of its outstanding questions, and explore its outward-facing aspects.This project will address major open problems such as determining whether Hindman's Theorem holds arithmetically, and whether it is equivalent to its restriction to sums of length at most two; determining the first-order part of Ramsey's Theorem for pairs, and clarifying the computability-theoretic relationship between this principle and its stable version; and determining the exact proof-theoretic strength of Laver's Theorem. More importantly, it will focus on the development of lines of research particularly relevant to the growing interest in connections between computability theory and combinatorics, including the study of questions of methodological interest to combinatorialists, for instance ones involving Hindman's Theorem and the use of ultrafilters in combinatorics; the development of new proofs of combinatorial theorems inspired by questions regarding the computational content of these theorems, along the lines of Montalban's new proof of Laver's Theorem; the analysis and comparison of different general methods, such as the use of ultrafilters, topological dynamics, and probabilistic methods; the development of notions of comparison between theorems that, while still computability-theoretic in spirit, are closer to being direct reflections of combinatorial differences; the understanding of splittings of combinatorial principles into computationally and combinatorially simpler parts; the study of the usefulness of combinatorially-defined objects as computational oracles; and the study of the first-order consequences of the existence of combinatorially-defined second-order objects. This project is thus aimed at developing the study of the connections between computability theory and combinatorics along a large number of related directions, making use of the computability-theoretic, proof-theoretic, and combinatorial expertise of its PIs, senior personnel, and key collaborators.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

计算理论是通过图灵和其他对算法概念的数学精确定义的发展而产生的。该领域最富有成果的发展之一是研究数学算法含量。同时，对数学基础的担忧导致了对数学推理的不同形式系统的分析，并研究了此类系统的相对力量。事实证明，可计算性理论方法在该项目中起着关键作用。组合学是数学领域，其方法和结果是大量数学推理的基础，因此研究其算法含量以及正式化其方法所需的系统尤为重要。可计算的组合学具有悠久的历史，但最近发现了兴趣的激增，强调了以下事实：理论上自然概念倾向于自然自然，反之亦然。该项目旨在通过提高我们对组合原理算法内容的理解，通过一致的小组努力来利用我们近年来进一步实现该领域的知识来加强对组合原理算法内容的理解，努力解决其出色的问题，并探索其外向项目的主要问题，以确定是否要确定hInder andh hinder and，相当于其限制到长度总和最多；确定Ramsey定理的成对的一阶部分，并阐明该原理与其稳定版本之间的可计算性理论关系；并确定Laver定理的确切理论强度。更重要的是，它将集中于与计算性理论与组合学之间对联系日益增长的兴趣有关的研究领域的发展，包括研究与组合主义者的方法论兴趣问题，例如涉及Hindman定理的研究者以及在组合学中使用超级动物的方法；合并定理的新证明的发展，其灵感来自有关这些定理的计算内容的问题，以及蒙塔尔班（Montalban）的Laver定理的新证明；不同一般方法的分析和比较，例如使用超滤波器，拓扑动态和概率方法；定理之间比较概念的发展，尽管在精神上仍然可计算性理论，但更接近组合差异的直接反映；将组合原理分裂成计算和组合更简单的部分的理解；将组合定义的对象作为计算齿轮的有用性的研究；以及组合定义的二阶对象存在的一阶后果的研究。因此，该项目的目的是在大量相关方向上开发对可计算理论与组合学之间的联系的研究，利用其PIS，高级人员和主要合作者的可计算性理论，证明理论和组合专业知识。该奖项通过评估了NSF的法定任务，并通过评估了Infactiria crigia and Founlitial的支持，这反映了NSF的法定任务。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Ramsey’s theorem and products in the Weihrauch degrees

拉姆齐定理和 Weihrauch 度的乘积

DOI：
10.3233/com-180203
发表时间：
2020
期刊：
Computability
影响因子：
0.6
作者：
Dzhafarov, Damir D.;Goh, Jun Le;Hirschfeldt, Denis R.;Patey, Ludovic;Pauly, Arno
通讯作者：
Pauly, Arno

COH, SRT 2 2 , and multiple functionals

COH、SRT 2 2 和多功能