Mathematical Sciences: Some Recursion Theoretic Problems

如果一个集合的元素有一个可计算的枚举，那么这个集合就是递归可枚举的。一个r.e.集合也有一个称为图灵度的信息内容；具有最大信息量的r.e.集称为图灵完备。r.e.集合的集合形成一个格，这个格是将r.e.集合作为集合来研究的最自然的设置。r.e.集合的一个性质是不变的，如果它被这个格的所有自同构所遵守。这个项目将研究不变集，和这个格的自同构，以及它们与r.e.集的度的关系。特别地，它将继续Soare最近的研究，研究不自同构于任何完备集的r.e.集（希望找到一些一般的不变集类），以及研究自同构于完备集的r.e.集（希望找到一些自同构的一般构造）。递归理论将抽象模型视为可计算性，忽略了时间和空间的实际限制。换句话说，如果内存和运行时需求只是有限的，而不考虑它们实际上有多大，那么根据这个模型，某些东西在理论上是可计算的。这种简化允许更深入地理解可计算性的本质。此外，同样清楚的是，在某些可以被证明不可递归计算的情况下，它当然也被证明在任何实际意义上都不可计算。最后，通过研究递归理论而养成的思维习惯也被证明是具有实用价值的，这位研究者以前的学生可以在从事软件开发的行业中找到，也可以在数学系培养下一代逻辑学家。

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.