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.

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