Computability, Enumerability, Decidability and Definability

该项目涉及可计算性理论领域的研究，包括关于整数集的经典可计算性理论，以及在其他数学领域的应用，特别是代数和逻辑。重点讨论结构一阶理论的可决性问题；有限子结构的表征；非平凡自同构的存在性与可定义性质代数中不可判定问题的分类。可计算性理论早于现代计算机的存在，始于20世纪30年代哥德尔的开创性工作。它研究了计算的理论界限（忽略了对内存空间和运行时间的限制），从而为计算机科学中的许多应用提供了理论框架。经典可计算性理论侧重于整数（被认为是来自许多数学领域的编码自然问题），并试图根据整数的复杂性对整数集进行分类。应用可计算性理论试图将这些方法应用于数学和计算机科学许多领域的自然问题。

This project involves research in the area of computability theory, both classical computability theory on the set of integers, and applications to other fields of mathematics, in particular algebra and logic. The focus is on questions of decidability of the first-order theory of structures; the characterization of finite substructures; the existence of nontrivial automorphisms versus definable properties; and the classification of undecidable problems in algebra. Computability theory predates the existence of modern computers, starting with the ground-breaking work of Goedel in the 1930's. It investigates the theoretical bounds of computation (neglecting restrictions on memory space and run time), thus providing the theoretical framework for many applications in computer science. Classical computability theory focuses on the integers (thought of as coding natural problems from many areas of mathematics) and tries to classify sets of integers by their complexity. Applied computability theory tries to apply these methods to natural problems in many areas of mathematics and computer science.