The principal investigator and her students and collaborators use computability theoretic methods to investigate various algorithmic phenomena on countable mathematical structures. The project aims to better understand how algebraic properties of structures interact with the algorithmic ones. Topics of investigation include: complexity of structures and their isomorphic copies, complexity of additional relations on their domains, complexity and structure of partial and total isomorphisms, and the correspondence between computability and definability. The complexity is often expressed by computable infinitary formulae, and measured by Turing degrees or by other computability theoretic degrees. Since these degrees are not invariant under isomorphisms, we investigate their spectrum, which consists of all degrees in the isomorphism type of a structure. An important goal is to relate the degree spectra of relations to the degree spectra of structures by studying the so-called spectrally universal structures. The project involves investigations in general model theoretic setting, such as algorithmic versions of categoricity, but also more concrete well-known classes of algebraic structures, such as commutative groups, non-commutative groups, rings, fields, vector spaces. Another goal of the project is to integrate computable algebra with algorithmic learning theory in Putnam-Gold's framework of inductive inference machines, which has so far been developed mainly for computably enumerable sets. This study is also important in the philosophy of inductive reasoning.
In the 1930's, Turing, Goedel, Kleene and others developed the mathematical theory of computability. Their results paved the way for the invention of modern computers. Model theory, which emerged as a distinct field in the 1940's through the works of Skolem, Goedel, Tarski, Malcev and others, provides a rigorous framework for the notions of language, meaning and truth. A model, a concept used in all of sciences, describes a portion of reality by using a formal language to express properties under study. Interaction of computability theory with model theory, as well as other areas of mathematics, has resulted in computable model theory and, more generally, in computable mathematics. Goedel's incompleteness theorem is a striking early result in computable model theory. While some mathematical constructions are algorithmic, or can be replaced by algorithmic ones yielding the same results, others are intrinsically non-algorithmic. Problems that can be solved algorithmically are called decidable. Examples of negative results in computable mathematics include the undecidability of the Hilbert's tenth problem, and the undecidability of the word problem in combinatorial group theory. Undecidable problems can be more precisely classified by considering generalized algorithms, which require external knowledge. Turing degrees, which play a significant role in this project, provide an important measure of the level of such knowledge needed. An important goal of the project is to use Turing degrees to investigate structures of importance in other areas of mathematics.
