Definability and Automorphisms in Computability Theory

可计算性理论中的可定义性和自同构

• 批准号: 0245167
• 负责人: Peter Cholak
• 金额: $ 36.29万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0245167&HistoricalAwards=false
• 关键词: Definability; Automorphisms; Computability; Theory

AbstractAward: DMS-0245167Principal Investigator: Peter A. CholakThe principal investigator plans to study the relationshipbetween definability and automorphisms in various structuresarising in computability theory. Primarily, but not totally, hewill focus on the collection of all computably enumerable sets.The principal investigator will also consider the collection ofall Pi01 classes and the computably enumerable degrees. A longrange goal is to provide a complete understanding of thesestructures and their automorphisms and definable orbits. Somerelated projects in computable structure theory and models ofsecond order arithmetic are also planned.The main focus of these projects is on definability andcomputability. These notions are both important in measuring thecomplexity of an answer to a mathematical problem. Problems suchas "Is there a computer program which can solve all questions ofthis type?" One develops an intertwined hierarchy ofdefinability and computability. Only answers which lay on thelowest level are computable and even then they are not alwaysfeasibly computable given today's computers. Answers of highercomplexity provide useful mathematical information, allow one totest the limits of mathematical techniques, reveal whether thewrong techniques are being used, and, in some very rare cases,can be useful for encoding/decoding information.

摘要：项目负责人：Peter A. cholak，主要研究可计算理论中出现的各种结构的可定义性和自同构之间的关系。他将主要（但不是全部）关注所有可计算枚举集合的集合。首席研究员还将考虑所有Pi01类和可计算枚举学位的集合。长期目标是提供对这些结构及其自同构和可定义轨道的完整理解。规划了可计算结构理论和二阶算法模型的相关课题。这些项目的主要焦点是可定义性和可计算性。这两个概念在测量数学问题答案的复杂性时都很重要。诸如“有没有一种计算机程序可以解决所有这类问题？”一种是可定义性和可计算性交织在一起的层次结构。只有在最低层次上的答案是可计算的，即使是这样，考虑到今天的计算机，它们也不总是可行的。高复杂性的答案提供了有用的数学信息，允许人们测试数学技术的极限，揭示是否使用了错误的技术，并且在一些非常罕见的情况下，可以用于编码/解码信息。