Computability, Reverse Mathematics, and Information Coding

University Of Chicago, Chicago IL

Investigators

Abstract

In the first half of the last century, Turing and others developed a mathematically precise definition of the notion of algorithm, or computer program. Modern computability theory and theoretical computer science grew out of these efforts, and led in particular to an interest in studying the computational content of mathematics. At the same time, developments in the foundations of mathematics led to the investigation of the relative power of different formal systems for mathematical reasoning. These two areas of inquiry turn out to be closely related, and this project is concerned with questions at their intersection. It aims to further our understanding of how structure affects computability, and how computability interacts with other fundamental notions such as randomness, the power of formal systems, and the interactions between formal systems and the mathematical structures they describe. In particular, this project lies in two related areas: computable mathematics and reverse mathematics of combinatorial, model theoretic, and related principles; and notions of robust information coding, including their connections with algorithmic randomness. Reverse mathematics and computable mathematics are closely related and complementary approaches to calibrating the strength of theorems and constructions throughout mathematics, and revealing the fundamental structure behind them. The investigation of combinatorial and model-theoretic principles from this point of view has proved to be a particularly rich line of research, and this project will pursue it from several angles, for instance the study of first order consequences of second order principles and notions of computability theoretic reduction that provide a particularly fine-grained analysis of the comparative strength of mathematical statements. Several of the combinatorial principles that play a central role in this area concern the existence of particular kinds of subobjects, which leads to a natural connection with the investigation of notions of robust information coding, which are reducibilities capturing the idea of being able to obtain partial information about an object from partial information about another. This project will further the study of these notions, in particular versions of infinite information reducibility, which are particularly closely connected with the computability theoretic aspects of versions of Ramsey's Theorem, and versions of coarse reducibility, which have already been found to have significant connections with algorithmic randomness.