Computability Theory

可计算性理论

• 批准号: 0555381
• 负责人: Steffen Lempp
• 金额: --
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0555381&HistoricalAwards=false
• 关键词: Computability; Theory

Computability theory is the area of mathematical logic studying effectiveness in mathematics. It also investigates the close connections between computability, definability, and provability, and thus the roles of language and proof in mathematical research, two of the central topics of logic overall. Classical computability theory studies the information content of sets of integers (considered as coding natural mathematical problems), while applied computability theory investigates the question to what extent constructions, mainly from algebra and model theory, can be carried out effectively. In addition, computability theory gives insight into questions from other parts of mathematical logic, in particular in proof theory and in model theory. Lempp proposes to investigate in particular the following aspects: 1. What can methods from computability theory tell us about quantifier bounds for axiomatizations of uncountably categorical theories? 2. How can one characterize computable models in terms of classical invariants, in particular Ketonen invariants for Boolean algebras and Ulm invariants for reduced abelian p-groups? 3. What is the proof-theoretic strength of principles from infinitary combinatorics, e.g., variants of Ramsey's Theorem, where new proof-theoretic principles seem to be most prevalent? 4. What is the algebraic structure of various degree structures, coding noncomputable sets of integers by relative computability?Computability theory is the area of mathematical logic studying effectiveness in mathematics; it can be viewed as an attempt to bridge and clarify the gap between "classical" mathematics and "effective" mathematics, given that the former has moved away more and more from an algorithmic to a more abstract "axiomatic" point of view. At the same time, computability theory compares effectiveness with how well mathematical objects can be described in a formal mathematical language, and how easily mathematical statements can be proved in a formal mathematical system, two of the central topics of mathematical logic overall. Lempp proposes to study these notions for a number of examples, particularly from modern algebra (e.g. groups and Boolean algebras) and from combinatorics. At the same time, Lempp plans to continue his investigation in degree theory, studying relative notions of computability and noncomputability and thus exploring the theoretical limitations of physical computing devices.

可计算性理论是研究数学有效性的数理逻辑领域。它还研究了可计算性、可定义性和可证明性之间的密切联系，以及语言和证明在数学研究中的作用，这是逻辑学的两个核心主题。经典可计算性理论研究整数集的信息内容（被视为编码自然数学问题），而应用可计算性理论则研究主要来自代数和模型理论的构造可以在多大程度上有效地进行的问题。此外，可计算性理论还可以洞察数理逻辑其他部分的问题，特别是证明论和模型论中的问题。 Lempp 建议特别研究以下几个方面： 1. 可计算性理论的方法可以告诉我们关于不可数分类理论公理化的量词界限的什么？ 2. 如何用经典不变量来描述可计算模型，特别是布尔代数的 Ketonen 不变量和简化阿贝尔 p 群的 Ulm 不变量？ 3. 无限组合学原理的证明理论强度是多少，例如，拉姆齐定理的变体，其中新的证明理论原理似乎最普遍？ 4. 通过相对可计算性对不可计算的整数集进行编码的各种度数结构的代数结构是什么？可计算性理论是研究数学有效性的数理逻辑领域；它可以被视为弥合和澄清“经典”数学和“有效”数学之间差距的尝试，因为前者已经越来越从算法观点转向更抽象的“公理化”观点。同时，可计算性理论将有效性与用形式数学语言描述数学对象的能力以及在形式数学系统中证明数学陈述的容易程度进行比较，这是数理逻辑的两个核心主题。 伦普建议通过许多例子来研究这些概念，特别是现代代数（例如群和布尔代数）和组合数学。与此同时，伦普计划继续他对度理论的研究，研究可计算性和不可计算性的相关概念，从而探索物理计算设备的理论局限性。