Mathematical Sciences: Computability Theory and Logic

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

9400825 Soare In this project Robert Soare will study recursion theory, namely the theory of computability on sets of integers, particularly relative computability of one set from another. The fundamental aim is to deepen our understanding of computability and its relation to algebraic structures and to models of various first order theories. The approach is to apply algebraic and model theoretic methods to assemble apparently unrelated and often chaotic individual results in recursion theory into a unified theory and to point the way toward future research. A recent example is the Slaman-Soare result where a simple algebraic criterion was discovered which unified many results and methods on the r.e. degrees over the last 30 years and solved the long standing problem on extension of embeddings. In another area Harrington and Soare have developed a method for generating automorphisms of the r.e. sets on the one hand and for producing definable properties on the other, which show that other automorphisms cannot exist. In addition, Lachlan and Soare have applied certain forcing methods to study models of arithmetic and will develop these further. The aim is to study computability of sets of integers. The first objective is to study computability in terms of the recursively enumerable (r.e.) sets, namely those which can be listed by a computable procedure, and to relate their algebraic structure to the degree of information they encode and to the speed with which they can be enumerated with respect to some measure of the complexity of computation. The second objective is to study the relationship of computability to other mathematical objects, for example to certain models, and to certain algebraic structures. For algebraic structures, the general problem is to determine exactly what information can be coded into a particular type of that structure. This will give new information about how information can be coded between sets and how it can be co ded into an algebraic structure. ***