Topics in Computable Structure Theory

可计算结构理论专题

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

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.

哈里扎诺夫和她的学生以及他们的合作者研究了代数、模型论和拓扑学中产生的一般和具体数学结构的算法特性。这需要可计算性理论与代数、拓扑学和几何学之间复杂的相互作用。哈里扎诺夫？的目标是理解可数结构及其同构的可计算性理论性质，以及结构域上的自然关系。她研究可定义性和可计算性之间的联系。结构的图灵度谱可以通过谱通用结构与关系的度谱相关，谱通用结构通常作为Fraisse极限获得。哈里扎诺夫？的项目包括可计算结构的模型理论复杂性，通过它们的斯科特等级来衡量。 它还包括分类问题，如同构问题和嵌入问题的自然类的代数结构。Harizanov研究了各种挠自由群的左序和双序，包括自由群、曲面和辫子群，以及序空间的拓扑性质如何与序的可计算性理论性质相关。该项目涉及可计算结构理论中重要的新方向，包括研究几何对象的同构类型的图灵度，如变种和方案，以及在低维拓扑中具有重要性的非关联二元运算的结构，如quandles。 可计算结构理论是一个非常活跃的研究领域，在过去的几十年里蓬勃发展。它在理论数学、计算机科学和数学哲学中具有重要意义。一些数学构造本质上是非算法的，而另一些则是算法的，或者可以被算法的构造所取代，从而产生相同的结果。 可计算性理论已经发展出强大而独特的技术来进一步分析和分类非算法的数学对象。这些方法涉及使用可计算无穷语言的语法描述，以及图灵和其他程度理论的相对计算复杂性的集合和问题，他们编码的措施。