权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Computable Mathematics Measured by Enumeration Degrees

用枚举度来衡量的可计算数学

基本信息

批准号：
2053848
负责人：
Mariya Soskova
金额：
$ 42万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-06-01 至 2025-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2053848&HistoricalAwards=false
关键词：
Computable Mathematics Measured Enumeration Degrees

项目摘要

Mathematical logic and computability arose from the need to develop stable and trustworthy foundations for mathematics, provide clear criteria for what constitutes a proof, what basic axioms give sufficient power to express the rest of mathematics, and what constitutes an algorithm or a computable function. The origins of the fields trace back to David Hilbert's program from the 1900's and to the work by Gödel, Church, and Turing that proved several aspects of this program impossible: there are problems in elementary number theory that do not have computable solutions. Since then, incomputable problems have been identified in many different subfields of mathematics. Most famously, the solution sets to some Diophantine equations and the word problem for some finitely presented groups are incomputable. Computability theory proposes frameworks to study the relative algorithmic complexity of such problems. This project proposes an in-depth investigation of two related frameworks in computability theory, and the complex structures that they give rise to. The project presents a diverse array of research avenues, suitable for all levels of experience. Soskova and Miller intend to continue their collaboration with undergraduate, graduate, and postgraduate students and facilitate the quick immersion of young researchers into this area through two textbooks: a beginner level Computability Theory textbook and a more specialized advanced textbook on the precise topic studied within this project. They also maintain a visual online database that allows the quick identification of open problems. The project will support women's engagement in the field through a mentorship program organized by Soskova within the CiE Women in Computability focus group. Soskova and Miller will continue to support the Logic Community by organizing scientific meetings and through their editorial work.In computability theory, the Turing degrees are used to measure the effective content of sets of natural numbers. This measure can be extended to capture the effective content of other objects in mathematics, such as the real numbers. In other cases, Turing reducibility is not sufficient. For example, Miller proved that it is not possible to assign a Turing degree to every continuous function on the unit interval. In that and many other cases, an extension of Turing reducibility, enumeration reducibility, turns out to provide a better framework for effective mathematics. In 1967, Rogers posed a list of problems that strongly influenced the development of computability theory. One of these problems asks whether the partial orders of the Turing degrees and the enumeration degrees are rigid structures, i.e., have no nontrivial automorphisms. Slaman and Woodin proved that the rigidity of the Turing degrees is equivalent to a complete characterization of its definable relations and to its biinterpretability with second order arithmetic. Building on this, Soskova proved that the same equivalence holds for the enumeration degrees. Miller and Soskova (with collaborators) answered another problem from the list: there is a first order definable copy of the Turing degrees inside the enumeration degrees. This established a link between the rigidity problems for the two structures; if the Turing degrees are rigid then so are the enumeration degrees. The rigidity of the enumeration degrees, while still open, could turn out to be more approachable. Definability within the enumeration degrees has already proved more approachable. The goal of this project is to expand our understanding of the structure of the enumeration degrees and its nontrivial connections to effective mathematics, with a focus on computable topology. We would like to accumulate new methods investigate combinatorial properties of the structure, and isolate special classes of degrees that determine the logical character of the structure.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.

数学逻辑和可计算性产生于需要发展稳定可靠的数学基础，为什么构成证明提供明确的标准，什么基本公理给予足够的力量来表达数学的其余部分，什么构成算法或可计算函数。这些领域的起源可以追溯到20世纪初大卫·希尔伯特的程序，以及Gödel、丘奇和图灵的工作，他们证明了这个程序的几个方面是不可能的：初等数论中有一些问题没有可计算的解。从那时起，不可计算问题在许多不同的数学分支领域中被发现。最著名的是，一些丢芬图方程的解集和一些有限表示群的词问题是不可计算的。可计算性理论提出了研究这类问题的相对算法复杂度的框架。这个项目提出了一个深入的研究在可计算性理论的两个相关框架，以及它们所产生的复杂结构。该项目提供了多样化的研究途径，适合所有水平的经验。Soskova和Miller打算继续他们与本科生、研究生和研究生的合作，并通过两本教科书促进年轻研究人员快速沉浸在这个领域：一本初级水平的可计算性理论教科书和一本更专业的高级教科书，关于这个项目所研究的精确主题。他们还维护一个可视化的在线数据库，可以快速识别未解决的问题。该项目将通过Soskova在CiE妇女可计算性焦点小组内组织的指导计划，支持妇女参与该领域。Soskova和Miller将继续通过组织科学会议和编辑工作来支持逻辑社区。在可计算性理论中，图灵度用来度量自然数集合的有效内容。这一措施可以扩展到捕捉数学中其他对象的有效内容，如实数。在其他情况下，图灵可约性是不充分的。例如，Miller证明了不可能给单位区间上的每个连续函数分配一个图灵度。在这种情况和其他情况下，图灵可约性的扩展，枚举可约性，为有效数学提供了一个更好的框架。1967年，罗杰斯提出了一系列问题，这些问题对可计算性理论的发展产生了重大影响。其中一个问题是图灵度和枚举度的偏序是否是刚性结构，即没有非平凡自同构。Slaman和Woodin证明了图灵度的刚性等价于图灵度的可定义关系的完整表征和二阶算法的双可解释性。在此基础上，Soskova证明了同样的等价性适用于枚举度。Miller和Soskova（与其合作者）回答了列表中的另一个问题：在枚举度内存在图灵度的一阶可定义副本。这在两个结构的刚度问题之间建立了联系；如果图灵度是刚性的，那么枚举度也是刚性的。枚举程度的刚性虽然仍然开放，但可能会变得更容易接近。在枚举度内的可定义性已经被证明是更容易接近的。这个项目的目标是扩展我们对枚举度的结构及其与有效数学的非平凡联系的理解，重点是可计算拓扑。我们希望积累新的方法来研究结构的组合性质，并分离出决定结构逻辑特征的特殊类度。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。