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 等价关系概念；和抽象复杂性理论。 该项目要解决的突出问题是一些与理论可计算性有关的问题。 它们存在于所谓的递归理论中，该理论涉及一种不受时间或空间限制的可计算性模型。 尽管这些问题的答案能够阐明实际问题，但只有当答案是否定的时候，它们才真正实用，因为说即使对可用资源没有限制，某些东西也无法计算，这确实是一个非常有力的陈述。目的。 可计算性理论的更精细结构有时与实际计算更相关，并且也会考虑其各个方面。