Mathematical Sciences: Computability Theory and Logic

在这个项目中，Robert Soare将研究递归理论，即整数集的可计算性理论，特别是一个集合与另一个集合的相对可计算性。基本目的是加深我们对可计算性及其与代数结构和各种一阶理论模型的关系的理解。该方法是运用代数和模型理论的方法，将递归理论中看似不相关的、经常是混乱的单个结果组合成一个统一的理论，并为未来的研究指明方向。最近的一个例子是Slaman-Soare结果，该结果发现了一个简单的代数准则，统一了近30年来在r.e.度上的许多结果和方法，解决了长期存在的嵌入可拓问题。在另一个领域，Harrington和Soare开发了一种方法，一方面生成正则集的自同构，另一方面产生可定义的性质，这表明其他自同构不可能存在。此外，Lachlan和Soare应用了一些强制方法来研究算术模型，并将进一步发展这些模型。目的是研究整数集的可计算性。第一个目标是研究递归可枚举（r.e.）集合的可计算性，即那些可以通过可计算过程列出的集合，并将它们的代数结构与它们编码的信息程度以及相对于计算复杂性的某些度量来枚举它们的速度联系起来。第二个目标是研究可计算性与其他数学对象的关系，例如与某些模型和某些代数结构的关系。对于代数结构，一般的问题是确定哪些信息可以编码到该结构的特定类型中。这将提供关于如何在集合之间编码信息以及如何将信息编码成代数结构的新信息。＊＊＊

9400825 Soare In this project Robert Soare will study recursion theory, namely the theory of computability on sets of integers, particularly relative computability of one set from another. The fundamental aim is to deepen our understanding of computability and its relation to algebraic structures and to models of various first order theories. The approach is to apply algebraic and model theoretic methods to assemble apparently unrelated and often chaotic individual results in recursion theory into a unified theory and to point the way toward future research. A recent example is the Slaman-Soare result where a simple algebraic criterion was discovered which unified many results and methods on the r.e. degrees over the last 30 years and solved the long standing problem on extension of embeddings. In another area Harrington and Soare have developed a method for generating automorphisms of the r.e. sets on the one hand and for producing definable properties on the other, which show that other automorphisms cannot exist. In addition, Lachlan and Soare have applied certain forcing methods to study models of arithmetic and will develop these further. The aim is to study computability of sets of integers. The first objective is to study computability in terms of the recursively enumerable (r.e.) sets, namely those which can be listed by a computable procedure, and to relate their algebraic structure to the degree of information they encode and to the speed with which they can be enumerated with respect to some measure of the complexity of computation. The second objective is to study the relationship of computability to other mathematical objects, for example to certain models, and to certain algebraic structures. For algebraic structures, the general problem is to determine exactly what information can be coded into a particular type of that structure. This will give new information about how information can be coded between sets and how it can be co ded into an algebraic structure. ***