Computability Theory and Algebraic Structures

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

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.