Computability on Cones

锥体上的可计算性

• 批准号: 1954062
• 负责人: Antonio Montalban
• 金额: $ 21万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1954062&HistoricalAwards=false
• 关键词: Computability; Cones

Computability theory is an area within mathematical logic that studies the complexity of countable mathematical objects. In mathematics, as we all know, some objects, constructions, or proofs are more complicated than others. Logicians have developed various ways of measuring this complexity. When one is interested in countable objects, which are central to a wide range of mathematics, the tools to measure these complexities come from computability theory. The objective of this project is to draw connections between complexity issues and structural issues to improve understanding of what forms complexity can take. The investigator will also continue work on a book series that aims to make it easier for the logic community to learn about the subject of computable structure theory, to help graduate students reach a research-level understanding of the subject, and to provide researchers with a modern reference.The main component of this project is the study of the structure that emerges when considering computability theoretic properties on a cone, that is, properties that hold relative to almost every oracle with respect to Martin's measure. The project will study generalizations of the uniform Martin's conjecture and the almost-everywhere structure of Turing equivalence. The study of on-a-cone properties led to structural characterizations for a variety of notions from computable structure theory over the last decade. This project investigates the one-a-cone structure of the Turing degrees, of Turing equivalence, and of other recursion theoretic objects. The research will pursue two lines of inquiry. On the one hand, recent work suggests Martin's conjecture is just the tip of the iceberg, and that there are other situations where one can get a nice structural classification of relativizable objects. This research will search further for such structural classifications for equivalence relations other than Turing equivalence. On the other hand, conjectures about properties of the Turing equivalence and its interactions with its sub-equivalence relations may provide information on where Turing equivalence is located in the landscape of Borel equivalence relations, and the project will investigate this possibility.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.

可计算性理论是数理逻辑中研究可数数学对象复杂性的一个领域。在数学中，我们都知道，有些对象、结构或证明比其他的更复杂。逻辑学家已经开发出各种方法来衡量这种复杂性。当人们对可数对象感兴趣时，可数对象是广泛数学的核心，衡量这些复杂性的工具来自可计算性理论。这个项目的目标是在复杂性问题和结构问题之间建立联系，以提高对复杂性可以采取的形式的理解。研究人员还将继续编写一系列丛书，旨在使逻辑学界更容易地学习可计算结构理论这一主题，帮助研究生对该主题达到研究水平的理解，并为研究人员提供现代参考。该项目的主要组成部分是研究当考虑锥体上的可计算性理论性质时出现的结构，即相对于几乎每个先知关于马丁的度量的性质。该项目将研究一致马丁猜想的推广和图灵等价的几乎处处结构。在过去的十年里，对锥上性质的研究导致了可计算结构理论中的各种概念的结构表征。这个项目研究了图灵度、图灵等价性和其他递归理论对象的一元一锥结构。这项研究将遵循两条路线进行调查。一方面，最近的研究表明，马丁的猜想只是冰山一角，还有其他情况可以很好地对可相对化的对象进行结构分类。本研究将进一步寻找图灵等值以外的等值关系的结构分类。另一方面，关于图灵等价的性质及其与次等价关系的相互作用的猜想可能提供图灵等价在Borel等价关系中的位置的信息，该项目将调查这种可能性。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

The tree of tuples of a structure

结构体的元组树

• 发表时间: 2020
• 期刊: The journal of symbolic logic
• 作者: Harrison-Trainor, M.;Montalbán, A.
• 通讯作者: Montalbán, A.

The determined property of Baire in reverse math

逆向数学中贝尔的确定性质

• DOI: 10.1017/jsl.2019.64
• 发表时间: 2020
• 期刊: Journal of symbolic logic
• 影响因子: 0.6
• 作者: Astor, E. P.;Dzhafarov, D.;Montalbán, A.;Solomon, R.;Westrick, L. B.
• 通讯作者: Westrick, L. B.