Computable Mathematics

点击翻译按钮获取中文摘要

In this project the principal investigator will apply methods fromcomputability theory and other branches of logic and theoretical computerscience to study the effective content and proof-theoretic strength ofvarious areas of mathematics. In particular, he will concentrate oneffective randomness, computable model theory, and reverse mathematics andeffectiveness of combinatorial principles. He will study the relativerandomness of reals, using methods from computability theory andalgorithmic information theory, concentrating in particular on theK-trivial reals, a natural class of reals that are far from random withwith many compelling properties and applications. In computable modeltheory, he will continue the development of methods to address issuesraised by effectivizing model-theoretic notions, including therelationships between the different ways that a given structure may beeffectivized; the relationships between the degree of effectivity ofdifferent models of theories with few models; and the degrees of specialmodels, such as prime, homogeneous, and saturated models, of completedecidable theories. He will also study computability-theoretic andproof-theoretic aspects of combinatorial principles such as versions ofRamsey's Theorem and principles related to partial and linear orderings,exploiting the connections between effective mathematics and the reversemathematics program.The study of the effective content of mathematics has received increasingattention in the last few decades. It is a natural outgrowth of theefforts to understand and formalize the notions of algorithm andcomputable function undertaken in the early part of the twentieth century.It is of both pure mathematical and foundational interest, and hasimportant connections with computer science. This project aims to furtherour understanding of how structure affects computability, and howcomputability interacts with other fundamental notions of modernmathematics and foundations of mathematics, such as randomness andproof-theoretic strength. Computability theorists have developed a highlysuccessful theory of relative computational complexity of sets of numbers,which, in addition to its intrinsic mathematical interest, has beeninfluential in theoretical computer science. One of the goals of thisproject is to continue the development of an emerging parallel theory ofrelative algorithmic randomness, which can act as a theoretical frameworkin which to consider questions such as: When should we say that aninfinite set is more random than another, and what consequences does therelative randomness of sets have for their relative computationalcomplexity?