Knight is continuing her work in recursive model theory. Over the past two years, she has obtained several results on degrees of models realizing prescribed sets of bounded complexity types (finitary or infinitary). The problem of characterizing the degrees of isomorphic copies of a given model now seems approachable. Knight and Slaman have a characterization for models of finite Scott height. The characterization is unpleasantly complicated, and they hope to simplify it. The recent results use a powerful method of Harrington. In addition to using the method to obtain further results, Knight hopes to come to a better understanding of the method itself. Ash developed a related method and proved a theorem giving general conditions under which his method works. Ash and Knight have begun trying to compare the two methods. All of these investigations shed further light on the theoretical limits of computing power, a matter that becomes increasingly relevant and fascinating as the actual limits of computing power expand with each generation of new machines.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Application #
8701559
Program Officer
Ralph M. Krause
Project Start
Project End
Budget Start
1987-06-15
Budget End
1990-11-30
Support Year
Fiscal Year
1987
Total Cost
$90,600
Indirect Cost
Name
University of Notre Dame
Department
Type
DUNS #
City
Notre Dame
State
IN
Country
United States
Zip Code
46556