Computability on Cones

可计算性理论是数学逻辑的一个领域，研究可数数学对象的复杂性。我们都知道，在数学中，有些对象、结构或证明比其他的要复杂得多。逻辑学家已经开发出各种方法来衡量这种复杂性。当一个人对数数对象感兴趣时，测量这些复杂性的工具来自可计算性理论。这个项目的目标是在复杂性问题和结构问题之间建立联系，以提高对复杂性可以采取何种形式的理解。研究者还将继续撰写一系列书籍，旨在使逻辑学社区更容易了解可计算结构理论这一主题，帮助研究生达到研究水平的理解，并为研究人员提供现代参考。这个项目的主要组成部分是研究在考虑锥上的可计算性理论性质时出现的结构，也就是说，与Martin的测量相关的几乎所有神谕都具有的性质。该项目将研究统一马丁猜想的推广和图灵等价的几乎无处不在的结构。在过去的十年中，对锥上性质的研究导致了可计算结构理论中各种概念的结构表征。本课题研究了图灵度、图灵等价和其他递归理论对象的单锥结构。这项研究将从两个方面展开。一方面，最近的研究表明，马丁的猜想只是冰山一角，在其他情况下，人们可以对可相对性物体进行很好的结构分类。本研究将进一步探索图灵等价以外的等价关系的结构分类。另一方面，关于图灵等价的性质及其与子等价关系的相互作用的推测可以提供图灵等价在Borel等价关系中所处位置的信息，该项目将研究这种可能性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.