Computability Theory and 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.