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.

摘要奖：DMS-0245167主要研究者：Peter A. Cholak首席研究员计划研究可计算性理论中出现的各种结构中的可定义性和自同构之间的关系。 主要的，但不是全部的，他将集中在所有可计算可排集的集合上。主要研究者也将考虑所有Pi 01类和可计算可排度的集合。 一个长期的目标是提供一个完整的理解这些结构和它们的自同构和可定义的轨道。 在可计算结构理论和二阶算术模型方面也计划了一些相关的项目，这些项目的主要焦点是可定义性和可计算性。 这两个概念在衡量数学问题答案的复杂性时都很重要。 问题，如“有没有一个计算机程序，可以解决所有的问题，这类？“一个人发展了一个可定义性和可计算性交织的层次结构。 只有最低层次的答案才是可计算的，即使这样，在今天的计算机条件下，它们也不总是可计算的。 高复杂度的答案提供了有用的数学信息，允许人们测试数学技术的极限，揭示是否使用了错误的技术，并且在一些非常罕见的情况下，可以用于编码/解码信息。