Computable Structure Theory

可计算结构理论

• 批准号: 1800692
• 负责人: Julia Knight
• 金额: $ 16.03万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1800692&HistoricalAwards=false
• 关键词: Computable; Structure; Theory

Knight works in computability theory, a branch of mathematical logic. There is a body of work designing procedures for computing certain functions, and there is work designing useful approximation procedures for other functions. There are many real-world functions (involving population, revenue, location of objects in space or events in time, etc.) that we can know only through approximations. Knight is particularly interested in computability and computable approximation in number systems and other algebraic structures. Traditionally, computability theory has dealt with countable objects. However, important algebraic structures such as the field of real numbers are uncountable. Some of the problems that interest Knight involve computability in uncountable structures. With Karen Lange and Reed Solomon, Knight is trying to measure the complexity of the process of finding roots of polynomials in fields of generalized power series. Some of the ideas go back to Newton. With Uri Andrews, Knight is interested in the problem of when an elementary first order theory that is well-behaved from the point of view of model theory has a computable model. Andrews and Knight have a result for "strongly minimal" theories, with conditions on the complexity of fragments of the theory guaranteeing that the countable models all have computable copies. For some cases, the models are produced by "workers" constructions, involving nested approximations. Knight is interested in applying the techniques of computability to uncountable structures. There are different approaches. Some involve changing the definition of what is computable. Noah Schweber defined a reducibility that allows us to compare the computing power of structures of arbitrary cardinality, using the standard computability notions. The idea is to collapse cardinals so that the structures being compared become countable.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.

奈特从事可计算性理论的研究，这是数理逻辑的一个分支。 有一个机构的工作设计程序计算某些功能，并有工作设计有用的近似程序的其他功能。 有许多现实世界的功能（涉及人口，收入，空间中的对象或时间中的事件的位置等）。我们只能通过近似来了解。 奈特对数字系统和其他代数结构中的可计算性和可计算近似特别感兴趣。 传统上，可计算性理论处理可数对象。 然而，像真实的数域这样重要的代数结构是不可数的。 一些问题的兴趣骑士涉及可计算性的不可数结构。 与卡伦兰格和里德所罗门，骑士正试图衡量复杂的过程中找到根的多项式领域的广义幂级数。 有些想法可以追溯到牛顿。 与乌里安德鲁斯，骑士感兴趣的问题时，一个基本的一阶理论，是行为良好的角度来看，模型理论有一个可计算的模型。 安德鲁斯和奈特对“强极小”理论有一个结果，条件是理论片段的复杂性保证可数模型都有可计算的副本。 在某些情况下，模型是由“工人”结构产生的，涉及嵌套近似。 奈特对将可计算性技术应用于不可数结构很感兴趣。 有不同的方法。 有些涉及到改变什么是可计算的定义。 Noah Schweber定义了一个约简，允许我们使用标准的可计算性概念来比较任意基数结构的计算能力。 该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Interpreting a field in its Heisenberg group

解释海森堡群中的域

• DOI: 10.1017/jsl.2021.107
• 发表时间: 2022
• 期刊: The Journal of Symbolic Logic
• 作者: Alvir, R.;Calvert, W.;Goodman, G.;Harizanov, V.;Knight, J.;Morozov, A.;Miller, R.;Soskova, A.;Weisshaar, R.
• 通讯作者: Weisshaar, R.

Copying one of a pair of structures

复制一对结构中的一个

• DOI: 10.1017/jsl.2021.89
• 发表时间: 2021
• 期刊: The Journal of Symbolic Logic
• 作者: Alvir, Rachael;Burchfield, Hannah;Knight, Julia F.
• 通讯作者: Knight, Julia F.

Expanding the reals by continuous functions adds no computational power

通过连续函数扩展实数不会增加计算能力

• 发表时间: 2022
• 期刊: JSL
• 作者: Andrews, U.;Knight, J. F..;Kuyper, R.;Miller, J. S.;and Soskova, M.
• 通讯作者: and Soskova, M.