Mathematical Sciences: The Structure of Relative Definability

数学科学：相对可定义性的结构

• 批准号: 9212022
• 负责人: Theodore Slaman
• 金额: $ 11.08万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-15 至 1995-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9212022&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Structure; Relative; Definability

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.

研究人员计划了几个项目，旨在阐明计算的动态特征，以及在不同环境中可计算性概念之间的联系。他设想分别研究各种度结构的整体理论；递归可枚举度的嵌入问题的扩展；图灵度中有限理想的勒曼定理的相对化表述；Kechris的泛Borel等价关系的概念；以及抽象复杂性理论。在这个项目要解决的问题中，突出的是一些与理论可计算性有关的问题。它们存在于所谓的递归理论中，该理论处理的是一种不受时间或空间限制的可计算性模型。虽然这些问题的答案具有启发实际问题的能力，但只有当答案是否定的时，它们才真正实用，因为如果说一些东西即使没有限制可用于此目的的资源也不能计算，这确实是一个非常强烈的声明。可计算性理论的精细结构有时与实际计算更相关，这一点的各个方面也将被考虑。