Computability and Mathematical Definability

DMS-9988644ABSTRACTSlaman建议研究可计算性和数学可定义性。Slaman的长期目标是完全理解与相对可定义性相关的度理论结构，如图灵度(D)和枚举度的全局结构，以及局部结构，如递归可枚举集(R)的Turing度，低于0‘的度，以及任意Scott集中表示的度。以D为范例，Slaman建议研究D的自同构群D内一阶可定义性的范围，以及D与真子理想之间的异同。斯拉曼建议研究可计算性和数学可定义性。通过对这些现象的定量数学分析，人们可以回答以下形式的问题：“有没有解决所有这种类型问题的算法？”“有没有具有特定性质的简单例子”，或“有具有这些性质的所有结构的具体分类吗？”人们甚至可以回答这样的问题：“这些技术足以解决这个问题吗？”人们必须发展一种算法理论来证明不存在某种类型的算法。同样，人们必须发展一个可定义性理论来证明没有简单的例子或具体的分类。在这个提议中，Slaman重点研究了图灵度：其中一个集合A高于另一个集合B的充要条件是当给定关于A的信息时，存在计算B的算法。图灵度是相对可计算性结构的抽象表示。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.