Topics in Computable Mathematics

可计算数学主题

• 批准号: 0904101
• 负责人: Valentina Harizanov
• 金额: $ 9.85万
• 依托单位: George Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2012-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0904101&HistoricalAwards=false
• 关键词: Topics; 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.

哈里扎诺夫运用可计算性理论的概念和方法来研究数学结构的各种算法性质如何与它们的代数和拓扑性质相互作用。哈里扎诺夫主要研究可数结构的复杂性，它们的同构，结构上的自然关系，以及可定义性和算法复杂性之间的联系。她既研究了模型理论背景下的一般结构，也研究了知名课程中的具体代数模型。哈里扎诺夫的工作涉及广泛的主题，包括结构的有效范畴、关系的图灵和强度谱、高Scott等级的可计算结构以及几何结构的同构类型的度。该项目还涉及到与泛代数密切相关的可计算数学的新方向，如研究自同构度谱和有效Frisse极限，以及与低维拓扑密切相关的新方向，如研究某些无挠群上的阶的复杂性。可计算数学是当前非常活跃的研究领域。它在理论数学、计算机科学和数学哲学中都具有重要意义。它将可计算性理论的思想和技术与其他数学领域的方法相结合，以解决重要的复杂性和分类问题。许多数学问题都有算法解决方案。对于那些根本不是算法的问题，我们使用复杂的、往往是独特的可计算性理论方法来进一步研究它们的计算内容。这些方法包括图灵等对集合及其所编码问题的相对计算复杂性的理论分析。