Topics in Computable Structure Theory

George Washington University, Washington DC

Investigators

Abstract

Harizanov and her students and their collaborators investigate algorithmic properties of general and concrete mathematical structures arising in algebra, model theory, and topology. This requires intricate interplay of computability theory with algebra, topology, and geometry. Harizanov?s goal is to understand the computability theoretic properties of countable structures and their isomorphisms, and of natural relations on the domains of the structures. She studies the connections between definability and computability. The Turing degree spectra of structures can be related to the degree spectra of relations via spectrally universal structures, which are often obtained as Fraisse limits. Harizanov?s project includes model-theoretic complexity of computable structures measured by their Scott rank. It also includes classification problems such as the isomorphism problem and the embedding problem for natural classes of algebraic structures. Harizanov studies the left orders and bi-orders of various torsion-free groups, including free groups, surface and braid groups, and how the topological properties of the spaces of orders relate to the computability-theoretic properties of orders. The project involves important new directions in computable structure theory, including the study of Turing degrees of the isomorphism types of geometric objects, such as varieties and schemes, and of structures with a nonassociative binary operation of importance in low-dimensional topology, such as quandles. Computable structure theory is a very active research area that has blossomed in the last few decades. It is of importance in theoretical mathematics and computer science and in the philosophy of mathematics. Some mathematical constructions are essentially nonalgorithmic, while the others are algorithmic, or can be replaced by algorithmic ones yielding the same results. Computability theory has developed powerful and unique techniques to further analyze and classify nonalgorithmic mathematical objects. Such methods involve syntactic descriptions using computable infinitary language, as well as Turing and other degree theoretic measures of relative computational complexity of sets and problems they encode.