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.

AbstractCholak计划研究数学逻辑中各种结构中的可确定性和可分配性之间的相互作用。 Cholak主要但并非完全是，Cholak将集中在包含关系和图灵降低性下的所有可计算值集合的集合上。 乔拉克（Cholak）的远距离观念是为了完全理解这两种结构及其自动形态和确定性的关系之间的关系。cholak的主要重点是确定性和可计算性。 这些努力对于测量答案的数学问题的复杂性都很重要。 一个人开发了一个交织在一起的层次结构，可定义性和可计算性。 只有在复杂度的最低级别上的答案是可以计算的，即使在当今计算机的情况下，也不总是可以计算。 高序列的答案提供了有用的数学信息，并允许USERTO测试其数学技术的限制。