Computability and Mathematical Definability

可计算性和数学可定义性

• 批准号: 9988644
• 负责人: Theodore Slaman
• 金额: $ 26.5万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-07-01 至 2005-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988644&HistoricalAwards=false
• 关键词: Computability; Mathematical; Definability

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.

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