Mathematical Sciences: Some Recursion Theoretic Problems

数学科学：一些递归理论问题

• 批准号: 9214048
• 负责人: Leo Harrington
• 金额: $ 18万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-01-15 至 1996-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9214048&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Some; Recursion; Theoretic

A set is recursively enumerable (r.e.) if there is a computable enumeration of its elements. An r.e. set also has an information content called its Turing-degree; an r.e. set with maximum information content is called Turing complete. The collection of r.e. sets form a lattice, and this lattice is the most natural setting for studying r.e. sets as sets. A property of r.e. sets is invariant if it is respected by all automorphisms of this lattice. This project will study invariant sets, and automorphisms of this lattice, and their relationship to the degrees of r.e. sets. In particular it will continue the recent research with Soare studying r.e. sets which are not automorphic to any complete set (with the hope of finding some general classes of invariant sets), and studying r.e. sets which are automorphic to a complete set (with the hope of finding some general constructions of automorphisms). Recursion theory treats an abstract model for computability that ignores practical limitations of time and space. In other words something is theoretically computable according to this model if memory and run-time requirements can be shown merely to be finite without regard to how large they might actually be. This simplification permits a deeper understanding of the nature of computability. Furthermore, it is also clear that in cases where something can be shown not to be recursively computable, it has certainly also been shown not to be computable in any practical sense. Finally, the habits of mind developed by the study of recursion theory turn out also to be of practical value, and former students of this investigator can be found in industry doing software development as well as in mathematics departments training another generation of logicians.

一个集合是递归可递归的（r.e.）如果有 其元素的可计算枚举。 一个r.e. set也有一个 信息内容称为图灵度; r.e.镶有 最大信息量称为图灵完备。 的 收集r.e.集合形成一个格子，这个格子就是 最自然的研究环境集合为集合。 的属性 R.E.集合是不变的，如果它被所有的自同构所尊重， 这个格子。 这个项目将研究不变集， 这个格的自同构，以及它们与 r.e.度集. 特别是它将继续最近的 研究与Soare研究r.e.不自守于 任何完整的集合（希望找到一些通用的类， 不变集），并研究r.e.自守于a的集合 完整的集合（希望找到一些通用的结构 自同构）。 递归理论将抽象模型视为可计算的 忽略了时间和空间的实际限制。 换句 根据这个模型，某个东西在理论上是可以计算的 如果存储器和运行时需求可以仅仅被示出为 而不考虑它们实际上有多大。 这 简化允许更深入地理解的性质， 可计算性 此外，很明显，如果 可以证明某个东西不是递归可计算的，它 当然也被证明是不可计算的，在任何实际的 道理啊 最后，通过学习， 递归理论也具有实用价值， 这位研究者的学生可以在工业界找到， 软件开发以及数学系的培训 新一代的逻辑学家