Computability on Cones

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

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.