Computability Theory and Algebraic Structures

可计算性理论和代数结构

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

The principal investigator and her students and collaborators usecomputability theoretic methods to investigate various algorithmicphenomena on countable mathematical structures. The project aims tobetter understand how algebraic properties of structures interact withthe algorithmic ones. Topics of investigation include: complexity ofstructures and their isomorphic copies, complexity of additionalrelations on their domains, complexity and structure of partial andtotal isomorphisms, and the correspondence between computability anddefinability. The complexity is often expressed by computableinfinitary formulae, and measured by Turing degrees or by othercomputability theoretic degrees. Since these degrees are not invariantunder isomorphisms, we investigate their spectrum, which consists of alldegrees in the isomorphism type of a structure. An important goal is torelate the degree spectra of relations to the degree spectra ofstructures by studying the so-called spectrally universal structures. The project involves investigations in general model theoretic setting,such as algorithmic versions of categoricity, but also more concretewell-known classes of algebraic structures, such as commutative groups,non-commutative groups, rings, fields, vector spaces. Another goal ofthe project is to integrate computable algebra with algorithmic learningtheory in Putnam-Gold's framework of inductive inference machines, whichhas so far been developed mainly for computably enumerable sets. Thisstudy is also important in the philosophy of inductive reasoning. In the 1930's, Turing, Goedel, Kleene and others developed themathematical theory of computability. Their results paved the way forthe invention of modern computers. Model theory, which emerged as adistinct field in the 1940's through the works of Skolem, Goedel,Tarski, Malcev and others, provides a rigorous framework for the notionsof language, meaning and truth. A model, a concept used in all ofsciences, describes a portion of reality by using a formal language toexpress properties under study. Interaction of computability theorywith model theory, as well as other areas of mathematics, has resultedin computable model theory and, more generally, in computablemathematics. Goedel's incompleteness theorem is a striking early resultin computable model theory. While some mathematical constructions arealgorithmic, or can be replaced by algorithmic ones yielding the sameresults, others are intrinsically non-algorithmic. Problems that can besolved algorithmically are called decidable. Examples of negativeresults in computable mathematics include the undecidability of theHilbert's tenth problem, and the undecidability of the word problem incombinatorial group theory. Undecidable problems can be more preciselyclassified by considering generalized algorithms, which require externalknowledge. Turing degrees, which play a significant role in thisproject, provide an important measure of the level of such knowledgeneeded. An important goal of the project is to use Turing degrees toinvestigate structures of importance in other areas of mathematics.

主要研究者和她的学生和合作者使用计算理论的方法来研究可数数学结构上的各种算法现象。 该项目旨在更好地理解结构的代数性质如何与算法性质相互作用。 调查的主题包括：结构及其同构副本的复杂性，它们的域上的加法关系的复杂性，部分同构和全同构的复杂性和结构，以及可计算性和可定义性之间的对应。 复杂性通常用可计算的无穷公式表示，用图灵度或其它可计算性理论度来度量。 由于这些度在同构下不是不变的，我们研究了它们的谱，它由同构型结构中的所有度组成。 一个重要的目标是通过研究所谓的谱泛结构将关系的度谱与结构的度谱联系起来。该项目涉及一般模型理论设置的调查，如算法版本的范畴，但也更具体的代数结构，如交换群，非交换群，环，域，向量空间。 该项目的另一个目标是将可计算代数与Putnam-Gold归纳推理机框架中的算法学习理论相结合，该框架迄今为止主要针对可计算可计算集合而开发。 这一研究在归纳推理的哲学中也很重要。在20世纪30年代，图灵、哥德尔、克莱因和其他人发展了可计算性的数学理论。 他们的成果为现代计算机的发明铺平了道路。 模型理论，作为一个独特的领域出现在20世纪40年代通过作品的Skolem，Goedel，Tarski，Malcev和其他人，提供了一个严格的框架概念的语言，意义和真理。 模型是所有科学中使用的一个概念，它通过使用一种形式语言来表达所研究的性质，从而描述了现实的一部分。 可计算性理论与模型论以及其他数学领域的相互作用，产生了可计算模型论，更一般地说，产生了可计算数学。 哥德尔不完全性定理是可计算模型理论中一个引人注目的早期结果。 虽然有些数学结构是算法的，或者可以被算法所取代，产生相同的结果，但其他数学结构本质上是非算法的。 可以用算法解决的问题被称为可判定的。 计算数学中的否定结果的例子包括希尔伯特第十问题的不可判定性，以及组合群论中的文字问题的不可判定性。 不可判定问题可以通过考虑需要外部知识的广义算法来更精确地分类。 图灵度在这个项目中起着重要的作用，它提供了一个衡量这种知识水平的重要尺度。 该项目的一个重要目标是使用图灵度来研究数学其他领域的重要结构。