Computable Mathematics

University Of Chicago, Chicago IL

Investigators

Abstract

In this project the principal investigator will apply methods from computability theory and other branches of logic and theoretical computer science to study the effective content and proof-theoretic strength of various areas of mathematics. In particular, he will concentrate on effective randomness, computable model theory, and reverse mathematics and effectiveness of combinatorial principles, with a particular emphasis on the connections between these areas. Among other areas in the theory of randomness, he will study properties of ``far from random'' sets and the connections between them and notions of mutual information for infinite strings. He will also seek further applications of randomness to various areas of computability theory. In computable model theory, he wl continue to address issues raised by effectivizing model theoretic notions, including the relationships between the degree of effectivity of different models of theories with few models and the computability theoretic and proof theoretic aspects of special models, such as prime, homogeneous, and saturated models. He will also further investigate computability theoretic and proof theoretic aspects of combinatorial principles as well as principles arising from model theory. In this work he will exploit the connections between effective mathematics and the reverse mathematics program, which aims to calibrate the strength of theorems of ordinary mathematics in terms of the (set existence and induction) axioms needed to prove them. The study of the effective content of mathematics has received increasing attention in the last few decades. It is a natural outgrowth of the efforts to understand and formalize the notions of algorithm and computable function undertaken in the early part of the twentieth century. It is of both pure mathematical and foundational interest, and has important connections with computer science. This project aims to further our understanding of how structure affects computability, and how computability interacts with other fundamental notions of modern mathematics and foundations of mathematics, such as randomness and proof-theoretic strength. Computability theorists have developed a highly successful theory of relative computational complexity of sets of numbers, which, in addition to its intrinsic mathematical interest, has been influential in theoretical computer science. One of the goals of this project is to continue the development of an emerging parallel theory of relative algorithmic randomness, which can act as a theoretical framework in which to consider questions such as: When should we say that an infinite set is more random than another, and what consequences does the relative randomness of sets have for their relative computational complexity?