Definability and Automorphisms in Computability Theory

摘要奖：DMS-0245167主要研究人员：Peter A.Cholak主要研究可计算性理论中各种结构中的可定义性和自同构之间的关系。主要，但不是全部，他将专注于所有可计算可枚举集的集合。首席调查者还将考虑所有Pi01类的集合和可计算可枚举度的集合。一个长远的目标是提供对这些结构及其自同构和可定义轨道的完整理解。还计划了可计算结构理论和二阶算法模型的相关项目，这些项目的主要重点是可定义性和可计算性。这两个概念在衡量数学问题答案的复杂性方面都很重要。“有没有一种计算机程序可以解决所有这类问题？”一种是开发可定义性和可计算性的相互交织的层次结构。只有位于最低层的答案才是可计算的，即便如此，考虑到当今的计算机，它们也并不总是可行的。复杂性较高的答案提供了有用的数学信息，允许人们测试数学技术的局限性，揭示是否使用了错误的技术，在某些非常罕见的情况下，可以用于编码/解码信息。

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.