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.