Computability Theory

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Computability theory is the area of mathematical logic studying effectiveness in mathematics. It also investigates the close connections between computability, definability, and provability, and thus the roles of language and proof in mathematical research, two of the central topics of logic overall. Classical computability theory studies the information content of sets of integers (considered as coding natural mathematical problems), while applied computability theory investigates the question to what extent constructions, mainly from algebra and model theory, can be carried out effectively. In addition, computability theory gives insight into questions from other parts of mathematical logic, in particular in proof theory and in model theory. Lempp proposes to investigate in particular the following aspects: 1. What can methods from computability theory tell us about quantifier bounds for axiomatizations of uncountably categorical theories? 2. How can one characterize computable models in terms of classical invariants, in particular Ketonen invariants for Boolean algebras and Ulm invariants for reduced abelian p-groups? 3. What is the proof-theoretic strength of principles from infinitary combinatorics, e.g., variants of Ramsey's Theorem, where new proof-theoretic principles seem to be most prevalent? 4. What is the algebraic structure of various degree structures, coding noncomputable sets of integers by relative computability? Computability theory is the area of mathematical logic studying effectiveness in mathematics; it can be viewed as an attempt to bridge and clarify the gap between "classical" mathematics and "effective" mathematics, given that the former has moved away more and more from an algorithmic to a more abstract "axiomatic" point of view. At the same time, computability theory compares effectiveness with how well mathematical objects can be described in a formal mathematical language, and how easily mathematical statements can be proved in a formal mathematical system, two of the central topics of mathematical logic overall. Lempp proposes to study these notions for a number of examples, particularly from modern algebra (e.g. groups and Boolean algebras) and from combinatorics. At the same time, Lempp plans to continue his investigation in degree theory, studying relative notions of computability and noncomputability and thus exploring the theoretical limitations of physical computing devices.