Computability Theory and Algebraic Structures

George Washington University, Washington DC

Investigators

Abstract

Harizanov integrates the ideas and methods from computability theory, model theory, algebra, and topology to investigate algorithmic phenomena on algebraic structures. She aims to better understand how algorithmic properties interact with algebraic and topological ones. Harizanov focuses on the complexity of countable models, their submodels and relations, and transformations of structures. She studies model-theoretic complexity of computable structures measured by their Scott rank. Harizanov investigates intrinsic complexity of relations on structures, captured both syntactically and by their Turing or strong degree spectra. She relates degree spectra of structures to the degree spectra of relations via spectrally universal structures, which are often obtained as Fraisse limits. Harizanov investigates the spaces of left orders and bi-orders on magmas, semigroups, and groups of importance in low-dimensional topology and algebra. She connects their topological properties with computability-theoretic ones. Harizanov also studies algorithmic complexity of isomorphisms. This includes effective categoricity of specific and general computable structures. It also includes the study of partial and total automorphisms. One direction is to develop the theory of automorphism degree spectra of computable structures. The other direction is to investigate various semigroups of partial automorphisms and how the structures can be recovered from these semigroups. Invented in the 1930's, computability theory paved the way for the creation of the modern programmable computer. The main thrust of the field is to understand the limitations on algorithmic computation, without regard for the physical implementation. Interaction of computability theory with model theory and universal algebra, as well as other areas of mathematics, has resulted in computable model theory and, more generally, in computable mathematics, a very active research area in the last few decades. Harizanov's proposed research includes a broad range of topics in computable mathematics. She investigates when some mathematical constructions are algorithmic, or can be replaced by algorithmic ones yielding the same results, and when they are fundamentally nonalgorithmic. Undecidable sets, as well as problems these sets encode, can be more precisely classified by considering algorithms with oracles, which require external knowledge. Turing and other computability-theoretic degrees, which play a significant role in Harizanov's project, provide an important measure of the level of such knowledge needed. Harizanov combines degree-theoretic and other unique methods from computability theory with algebraic, combinatorial and topological methods to study and explain phenomena of importance in other areas of mathematics.