This project includes research into a broad range of topics in computability theory (recursion theory) and into logic applied to various areas of computer science. Included in the first area are investigations of recursively enumerable sets, several structures of degrees of complexity from Turing to polynomial time, and the proof theoretic complexity of some mathematical theorems. The second area of research includes the analysis and development of a source in nonmonotonic logic, concurrent programming models, resource bounded logic, and applications of linear programming ideas and algorithms to data structures and logic programming. Both theoretical computability questions and more practical ones are addressed by this project. The theoretical ones are the ones in what is known as recursion theory, which deals with a model of computability knowing no bounds on time or space. Although answers to such questions have the ability to illuminate practical questions, they are really practical only when their answers are negative, for it is a very strong statement indeed to say that something cannot be computed even when one puts no limits on resources available for the purpose. The finer structure of computability theory is even more relevant to actual computations, and various aspects of that will also be considered.
