Mathematical Sciences: The Structure of Relative Definability

研究者计划了几个项目，旨在阐明计算的动态特征以及不同环境中可计算性概念之间的联系。他设想对各种学位结构的全球理论进行单独研究；递归可枚举度下嵌入问题的推广在图灵度上有限理想的Lerman定理的相对化表述；Kechris关于全称Borel等价关系的概念以及抽象的复杂性理论。在这个项目要解决的问题中，突出的是一些与理论可计算性有关的问题。它们存在于所谓的递归理论中，递归理论处理的是不受时间或空间限制的可计算性模型。虽然这些问题的答案有能力阐明实际问题，但只有当答案是否定的时候，它们才是真正实际的，因为即使在不限制可用资源的情况下，也不能计算某些东西，这确实是一个非常有力的说法。可计算性理论的精细结构有时与实际计算更相关，并且还将考虑其各个方面。

The investigator plans several projects designed to illuminate the dynamic features of computations and the connections between notions of computability in varying environments. He envisions separate studies on the global theory of various degree structures; the extension of embeddings problem for the recursively enumerable degrees; the relativized formulation of Lerman's theorem on finite ideals in the Turing degrees; Kechris' notion of universal Borel equivalence relations; and abstract complexity theory. Prominent among the questions to be addressed by this project are a number that bear on theoretical computability. They lie in what is known as recursion theory, which deals with a model of computability knowing no bounds on time or space. Although answers to such questions have the ability to illuminate practical questions, they are really practical only when their answers are negative, for it is a very strong statement indeed to say that something cannot be computed even when one puts no limits on resources available for the purpose. The finer structure of computability theory is sometimes more relevant to actual computations, and various aspects of that will also be considered.