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. ***

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
9400825
Program Officer
Ralph M. Krause
Project Start
Project End
Budget Start
1994-10-01
Budget End
1998-06-30
Support Year
Fiscal Year
1994
Total Cost
$190,127
Indirect Cost
Name
University of Chicago
Department
Type
DUNS #
City
Chicago
State
IL
Country
United States
Zip Code
60637