Mathematical Sciences: Recursion Theory

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

Lempp intends to pursue research in classical recursion theory. He plans to concentrate in the following areas: 1. Lempp, jointly with Lerman, plans to finish up a project on the decidability of the existential theory of the recursively enumerable (r.e.) degrees with nth jump reducibility predicates. 2. Lempp, jointly with Lerman, Shore, and Soare, plans to investigate the existence of isomorphic r.e. intervals , a partial result toward showing the existence of nontrivial automorphisms of the r.e. degrees. 3. Lempp, jointly with Ambos-Spies, will try to show that every r.e. interval has a non-aleph-0 categorical theory, a result known now only for the set of all r.e. degrees. 4. Lempp, jointly with Kucera and Lerman, will investigate the construction of r.e. degrees via diagonally nonrecursive functions, as an alternative to conventional priority arguments. These are topics of interest to experts in recursion theory, a theory which formalizes the notion of mechanically computable if given enough memory and enough time. Observe that this is not really the same as mechanically computable in some reasonable length of time, but answers to questions about the more general notion are often easier to obtain and do shed light on practical computability questions.