Computability and definability in mathematical logic

数理逻辑中的可计算性和可定义性

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

ABSTRACTCholak plans on studying the interaction between definability andcomputability in various structures in mathematical logic. Primarily,but not totally, Cholak will focus on the collection of all computablyenumerable sets under the inclusion relation and the computablyenumerable degrees under Turing reducibility. Cholak's long rangegoals are to provide a complete understanding of the relationshipsbetween these two structures and their automorphisms and definableorbits.Cholak's main focus is on definability and computability. Thesenotions are both important in measuring the complexity of an answer toa mathematical problem. One develops an intertwined hierarchy ofdefinability and computability. Only answers which lay on the lowestlevel of complexity are computable and even then are not alwaysfeasibly computable given today's computers. Answers of highercomplexity provide useful mathematical information and allows the userto test the limits of their mathematical techniques.

【摘要】cholak计划研究数理逻辑中各种结构的可定义性和可计算性之间的相互作用。Cholak将主要（但不是全部）关注包含关系下所有可计算枚举集的集合和图灵可约性下的可计算枚举度。Cholak的长期目标是提供对这两种结构及其自同构和可定义轨道之间关系的完整理解。Cholak主要关注的是可定义性和可计算性。这两种感觉在衡量数学问题答案的复杂性时都很重要。一种是可定义性和可计算性交织在一起的层次结构。只有复杂性最低的答案才是可计算的，即使是这样，对于今天的计算机来说，也并不总是可行的。更复杂的答案提供了有用的数学信息，并允许用户测试他们的数学技术的极限。