Mathematical Sciences: Some Recursion Theoretic Problems

点击翻译按钮获取中文摘要

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.