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