Computability and Mathematical Definability

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

DMS-9988644 ABSTRACT Slaman proposes to study computability and mathematical definability. Slaman's long term goal is to provide a complete understanding of the degree theoretic structures associated with relative definability, such as the global structures of the Turing degrees (D) and the enumeration degrees, as well as the local ones, such as the Turing degrees of the recursively enumerable sets (R), the degrees below 0', and the degrees represented within an arbitrary Scott set. Fixing D as a paradigm example, Slaman proposes to investigate the scope of first order definability within D, the automorphism group of D, and the similarities and dissimilarities between D and proper subideals. Slaman proposes to study computability and mathematical definability. With quantitative mathematical analysis of these phenomena, one can answer questions of the form ``Is there an algorithm to solve all problems of a this type?'', ``Is there a simple example with specific properties'', or ``Is there a concrete classification of all structures with these properties?''. One can even address questions of the sort ``Are these techniques adequate to resolve this question?''. One must develop a theory of algorithms to show that there is no algorithm of a certain type. Similarly, one must develop a theory of definability to show that there is no simple example or concrete classification. In this proposal, Slaman focuses on the Turing degrees: where one set A is above another B if and only if there is an algorithm to compute B when given information about A. The Turing degrees are an abstract representation of the structure of relative computability. Slaman proposes to study this structure, and to pay close attention to the extent that the degrees of the definable sets play a special role within it.