Computability and Mathematical Definability

Slaman提出研究可计算性和数学可定义性，他的长期目标是提供与相对可定义性相关的度理论结构的完整理解，如图灵度（D）和枚举度的全局结构，以及局部结构，如递归可枚举集（R）的图灵度，0 '以下的度，和任意斯科特集合中的度数。 以D为例，Slaman提出研究D中一阶可定义性的范围、D的自同构群以及D与真子理想的异同。 Slaman建议研究可计算性和数学可定义性。通过对这些现象的定量数学分析，人们可以回答这样的问题：“是否有一种算法可以解决这种类型的所有问题？”“”，“”是否有一个简单的例子与specificproperties“"，或”“是否有一个具体的分类所有结构与这些属性？''. 人们甚至可以提出这样的问题：“这些技术足以解决这个问题吗？”''. 人们必须发展一种算法理论，以表明不存在某种类型的算法。 同样，人们必须发展一种可定义性理论，以表明没有简单的例子或具体的分类。 在这个提议中，Slaman集中在图灵度上：其中一个集合A在另一个集合B之上当且仅当存在一个算法来计算B，当给定关于A的信息时。 Slaman提出要研究这种结构，并密切关注可定义集合的度在其中所起的特殊作用。

DMS-9988644ABSTRACTSlaman proposes to study computability and mathematical definability.Slaman's long term goal is to provide a complete understanding of thedegree theoretic structures associated with relative definability,such as the global structures of the Turing degrees (D) and theenumeration degrees, as well as the local ones, such as the Turingdegrees of the recursively enumerable sets (R), the degrees below 0',and the degrees represented within an arbitrary Scott set. Fixing Das a paradigm example, Slaman proposes to investigate the scope offirst order definability within D, the automorphism group of D, andthe similarities and dissimilarities between D and proper subideals. Slaman proposes to study computability and mathematical definability.With quantitative mathematical analysis of these phenomena, one cananswer questions of the form ``Is there an algorithm to solve allproblems of a this type?'', ``Is there a simple example with specificproperties'', or ``Is there a concrete classification of allstructures with these properties?''. One can even address questionsof the sort ``Are these techniques adequate to resolve thisquestion?''. One must develop a theory of algorithms to show thatthere is no algorithm of a certain type. Similarly, one must developa theory of definability to show that there is no simple example orconcrete classification. In this proposal, Slaman focuses on theTuring degrees: where one set A is above another B if and only ifthere is an algorithm to compute B when given information about A.The Turing degrees are an abstract representation of the structure ofrelative computability. Slaman proposes to study this structure, andto pay close attention to the extent that the degrees of the definablesets play a special role within it.