Mathematical Sciences: Recursive Function Theory

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

The investigator will continue research in several areas of recursive function theory, including: automorphisms and definable properties of the recursively enumerable (r.e.) sets; algebraic, model-theoretic, and definability questions concerning the r.e. Turing degrees; recursion-theoretic properties of various algebraic structures; and computational complexity questions for polynomially-time-bounded Turing degrees. Soare recently developed with Harrington and Lachlan a very powerful method for generating new automorphisms of the r.e. sets, and they simultaneously found several new definable properties which together with the automorphisms answered many fundamental questions going back to Post's program (1944) on the relationship between the algebraic structure of an r.e. set and its Turing degree. These two new methods will be developed further and applied to answer other open questions on r.e. sets. Soare will continue his study of questions of continuity, definability, embeddability, and partial decidability for the structure of the r.e. Turing degrees. He will complete research on computability aspects of various algebraic structures, specially Boolean algebras, investigating, for example, which information can be coded into their classical isomorphism types. Finally, he will continue research with several collaborators on computational complexity questions for the many-one and Turing degrees under polynomially-time-bounded Turing computations. The motivation for studying such notions lies in their origins. For example, Turing machines idealize actual computing devices, and Turing degrees simply order their relative computational power. The elaborate techniques required to prove theorems in this area sometimes tend to obscure these fundamental facts, despite an effort to use suggestive terminology, e.g., "computability" and "computational complexity."