Definability and Automorphisms in Computability Theory

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

Abstract Award: DMS-0245167 Principal Investigator: Peter A. Cholak The principal investigator plans to study the relationship between definability and automorphisms in various structures arising in computability theory. Primarily, but not totally, he will focus on the collection of all computably enumerable sets. The principal investigator will also consider the collection of all Pi01 classes and the computably enumerable degrees. A long range goal is to provide a complete understanding of these structures and their automorphisms and definable orbits. Some related projects in computable structure theory and models of second order arithmetic are also planned. The main focus of these projects is on definability and computability. These notions are both important in measuring the complexity of an answer to a mathematical problem. Problems such as "Is there a computer program which can solve all questions of this type?" One develops an intertwined hierarchy of definability and computability. Only answers which lay on the lowest level are computable and even then they are not always feasibly computable given today's computers. Answers of higher complexity provide useful mathematical information, allow one to test the limits of mathematical techniques, reveal whether the wrong techniques are being used, and, in some very rare cases, can be useful for encoding/decoding information.