权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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年前的模式是给计算机一个程序，然后运行直到它得到答案，而现在的模式不同了，程序在继续之前经常暂停并要求输入。因此，真正的计算模型，正如它被实践的那样，是带有神谕的图灵机。