Topics in Computable Mathematics

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

Harizanov applies computability theoretic concepts and methods to study how various algorithmic properties of mathematical structures interact with their algebraic and topological properties. Harizanov focuses on the complexity of countable structures, their isomorphisms, and natural relations on structures, and connections between definability and algorithmic complexity. She investigates both general structures in model theoretic setting, as well as concrete algebraic models from well-known classes. Harizanov works on a broad range of topics including effective categoricity of structures, Turing and strong degree spectra of relations, computable structures of high Scott rank, and degrees of the isomorphism types of geometric structures. The project also involves new directions in computable mathematics with close connections with universal algebra, such as the study of automorphism degree spectra and effective Fraisse limits, and with close connections with low-dimensional topology, such as the study of complexity of orders on certain torsion-free groups.Computable mathematics is currently a very active research area. It is of importance in theoretical mathematics and computer science and in the philosophy of mathematics. It combines ideas and techniques of computability theory with methods of other areas of mathematics to solve important complexity and classification problems. Many mathematical problems have algorithmic solutions. For those problems that are fundamentally non-algorithmic, we use sophisticated and often unique computability theoretic methods to further investigate their computational content. Such methods include Turing and other degree theoretic analysis of relative computational complexity of sets and problems they encode.