Mathematical Sciences: Recursively Enumerable Degrees and Priority Arguments

数学科学：递归可枚举度和优先级参数

• 批准号: 9200539
• 负责人: Manuel Lerman
• 金额: $ 12.6万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-07-15 至 1996-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9200539&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Recursively; Enumerable; Degrees

In degree theory, one tries to determine whether natural classes of oracles with differing information content have different algebraic properties. Thus questions about decidability of fragments of elementary theories of degree structures are pursued, in order to determine which degrees are definable, and how complicated the definitions must be. Rigidity questions, or questions about automorphisms of the structures are pursued, with the aim that if a structure is rigid, then sets with different information content do, in fact, look different algebraically. Such questions are within the scope of this project. The major tool of proof in recursion theory is the priority argument. A general framework for priority arguments at all levels is being sought, in the hope that a better understanding of priority arguments will assist in finding applications of this powerful combinatorial technique to real world problems. Computing, as it is practiced today, is of an interactive nature. Rather than the model of twenty years ago, where the computer was presented with a program and ran until it obtained an answer, the programs of today pause frequently and ask for input before continuing. Thus the true model of computing, as it is practiced, is the Turing machine with an oracle.

在度理论中，人们试图确定自然的 具有不同信息内容的各类神谕具有 不同的代数性质 因此关于决策性的问题 度结构的基本理论的片段， 为了确定哪些程度是可以定义的，以及如何定义， 定义一定很复杂 刚性问题，或 关于结构的自同构的问题被追求， 如果一个结构是刚性的， 事实上，信息量在代数上看起来确实不同。 这些问题都属于本项目的范围。 主要 递归论中的一个证明工具是优先论证。 一 正在制定各级优先论点的总体框架， 希望能更好地理解 论证将有助于找到这一强大的应用程序 组合技术来解决真实的世界问题。 计算，因为它是今天实践，是一个互动的 自然 而不是20年前的模式， 计算机被提交了一个程序，并运行，直到它获得一个 回答，今天的程序经常暂停，并要求输入 然后继续。 因此，真正的计算模型， 实践，是图灵机与甲骨文。