Computability Theory and Logic

University Of Chicago, Chicago IL

Investigators

Abstract

IN this project the investigator will study computability theory and its relationship and applications to other areas of mathematics such as differential geometry and algebraic structures, as well as internal computability properties such as automorphisms of computably enumerable (c.e.) sets and the effective content of mathematics. The space Riem(M) of Riemannian metrics (modulo diffeomorphisms) on certain manifolds is of considerable interest to a wide variety of mathematicians and physicists. Topologists have proved for certain natural scale invariant functionals related to diameter on the space Riem(M), and for certain manifolds M of dimension > 4 that for every c.e. set A there is a sequence of points x_n, n in N, the integers, such that if n in A then x_n determines a local minimum on Riem(M) whose depth is roughly equal to the halting time of the Turing machine computation that n in A. The investigator constructed an infinite sequence of sets A_i, i in N, of c.e. sets so that for all n the settling function (for stopping times of the associated Turing machine) of A_i dominates that of A_{i+1}, even when the latter is composed with an arbitrary computable function. The two results together give a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and those containing still smaller basins, and so on, where the relative size of one set of basins to the next exceeds any computable function, what the topologists describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization.'' The investigator's work will also stress connections of computability to model theory and algebraic structures. With a junior colleague and a graduate student he will classify the degree spectrum of models which are prime or saturated but which have no computable isomorphic copy. Finally, he will continue his work on the automorphisms and structure of c.e. sets. He will put together these results to help obtain a classification of structure of c.e. sets and effective content of certain parts of mathematics.