Computable Mathematics Measured by Enumeration Degrees

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

基本信息

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

项目摘要

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.
数学逻辑和计算源于需要为数学开发稳定且值得信赖的基础,为构成证据的内容提供明确的标准,基本公理提供了足够的能力来表达其余数学,以及构成算法或可计算功能的功能。这些领域的起源追溯到了1900年代的戴维·希尔伯特(David Hilbert)的计划,以及哥德尔(Gödel),教堂和图灵(Turing)的作品,证明了该计划的几个方面:基本数字理论中的问题没有可计算的解决方案。从那时起,在许多不同的数学子字段中都发现了无可损不解的问题。最著名的是,解决方案设置为某些二芬太汀方程,而对于某些最终提出的组来说,问题问题是无法任何型的。计算理论提出框架,以研究此类问题的相对算法复杂性。该项目提出对计算理论中两个相关框架的深入研究及其产生的复杂结构。该项目提出了一系列潜水员的研究途径,适合各个级别的经验。索斯科娃(Soskova)和米勒(Miller)打算继续与本科,研究生和研究生的本科生合作,并通过两本教科书快速浸入该领域:初学者级别的可计算性理论教科书和该项目中精确的研究录像带上的更专业的高级教科书。他们还维护了一个视觉在线数据库,该数据库允许快速识别开放问题。该项目将通过Soskova在CIE妇女在Comparitible Focus Group中组织的心态计划来支持妇女在该领域的参与。索斯科娃(Soskova)和米勒(Miller)将继续通过组织科学会议和编辑工作来支持逻辑社区。在计算理论中,图灵学位用于衡量一组自然数的有效内容。可以扩展此度量以捕获数学中其他对象的有效内容,例如实数。在其他情况下,减少图灵是不够的。例如,米勒(Miller)规定,在单位间隔上不可能为每个连续功能分配图灵度。在这种情况下,在许多情况下,减少图灵,减少枚举的扩展为有效数学提供了更好的框架。 1967年,罗杰斯(Rogers)提出了一系列问题,这些问题强烈影响了计算理论的发展。这些问题之一询问图灵程度和枚举程度的部分顺序是否是刚性结构,即没有非平凡的自动形态。 Slaman和Woodin证明了Turing度的刚性等同于其定义关系的完整表征以及其与二阶算术相关的生物矫正性。在此基础上,索斯科娃证明了枚举学位相同的等价性。米勒(Miller)和索斯科娃(Soskova)(与合作者)从列表中回答了另一个问题:枚举学位内有一阶的图灵学位副本。这建立了两个结构的刚性问题之间的联系。如果图灵度是刚性的,则枚举程度也是如此。枚举学位的刚性虽然仍然开放,但可能会更容易平易近人。枚举学位内的确定性已经证明更容易平易近人。该项目的目的是扩展我们对枚举学位结构及其非平凡联系与有效数学的理解,重点是可计算的拓扑。我们想累积新方法研究结构的组合特性,并分离确定结构逻辑特征的特殊阶层。该奖项反映了NSF的法定任务,并通过使用基金会的智力优点和更广泛的影响来评估NSF的法定任务。

项目成果

期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Complexity profiles and generic Muchnik reducibility
复杂性概况和通用的 Muchnik 可归约性
  • DOI:
    10.1016/j.aim.2023.109397
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Andrews, Uri;Miller, Joseph S.;Schweber, Noah;Soskova, Mariya
  • 通讯作者:
    Soskova, Mariya
Extensions of two constructions of Ahmad
  • DOI:
    10.3233/com-210380
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jun Le Goh;S. Lempp;K. Ng;M. Soskova
  • 通讯作者:
    Jun Le Goh;S. Lempp;K. Ng;M. Soskova
MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY
可计算性理论中的最大塔和超滤基
  • DOI:
    10.1017/jsl.2022.60
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    LEMPP, STEFFEN;MILLER, JOSEPH S.;NIES, ANDRÉ;SOSKOVA, MARIYA I.
  • 通讯作者:
    SOSKOVA, MARIYA I.
PA RELATIVE TO AN ENUMERATION ORACLE
PA 相对于枚举预言机
  • DOI:
    10.1017/jsl.2022.55
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    GOH, JUN LE;KALIMULLIN, ISKANDER SH.;MILLER, JOSEPH S.;SOSKOVA, MARIYA I.
  • 通讯作者:
    SOSKOVA, MARIYA I.
Expanding the reals by continuous functions adds no computational power
通过连续函数扩展实数不会增加计算能力
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Andrews, U.;Knight, J. F..;Kuyper, R.;Miller, J. S.;and Soskova, M.
  • 通讯作者:
    and Soskova, M.
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Mariya Soskova其他文献

Mariya Soskova的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Mariya Soskova', 18)}}的其他基金

Computing with Positive Information: Definability and Structure of Enumeration Degrees
正信息计算:枚举度的可定义性和结构
  • 批准号:
    1762648
  • 财政年份:
    2018
  • 资助金额:
    $ 42万
  • 项目类别:
    Standard Grant

相似国自然基金

复杂问题化学测量学数学分离基础理论及定量分析应用的深化研究
  • 批准号:
    22174036
  • 批准年份:
    2021
  • 资助金额:
    61.00 万元
  • 项目类别:
    面上项目
复杂问题化学测量学数学分离基础理论及定量分析应用的深化研究
  • 批准号:
  • 批准年份:
    2021
  • 资助金额:
    61 万元
  • 项目类别:
    面上项目
椭球几何学与任意高斯投影数学分析
  • 批准号:
    41871376
  • 批准年份:
    2018
  • 资助金额:
    57.5 万元
  • 项目类别:
    面上项目
基于整机运行精度与生产成本的数控机床关键零部件公差参数优化设计的理论方法与实验研究
  • 批准号:
    51775010
  • 批准年份:
    2017
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
基于“分离-整合”思想的摄影测量多特征统一处理模型与方法研究
  • 批准号:
    41701525
  • 批准年份:
    2017
  • 资助金额:
    25.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Control Systems Engineering to Address the Problem of Weight Loss Maintenance: A System Identification Experiment to Model Behavioral & Psychosocial Factors Measured by Ecological Momentary Assessment
解决减肥维持问题的控制系统工程:行为建模的系统识别实验
  • 批准号:
    10749979
  • 财政年份:
    2023
  • 资助金额:
    $ 42万
  • 项目类别:
Estimation of dynamic behavior of drill pipe for scientific drilling and its validation using measured data in actual drilling operation
科学钻井钻杆动态行为的估计及其在实际钻井作业中使用测量数据的验证
  • 批准号:
    17H03491
  • 财政年份:
    2017
  • 资助金额:
    $ 42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
Robust Aerodynamic Design Optimization considering Local Deformation based on Measured Data
基于测量数据考虑局部变形的稳健气动设计优化
  • 批准号:
    17K05148
  • 财政年份:
    2017
  • 资助金额:
    $ 42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
The modification of the car-following model through the introduction of the measured traffic flow characteristics and the evaluation of the highway traffic flow prediction by this model
通过引入实测交通流特征对跟驰模型进行修正并评价该模型对高速公路交通流的预测
  • 批准号:
    16K12540
  • 财政年份:
    2016
  • 资助金额:
    $ 42万
  • 项目类别:
    Grant-in-Aid for Challenging Exploratory Research
Study on locally compact quantum groups and measured groupoids
局部紧量子群与可测群形的研究
  • 批准号:
    22540215
  • 财政年份:
    2010
  • 资助金额:
    $ 42万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了