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。一个人如何以经典不变性来表征可计算的模型，特别是布尔代数和ULM不变性的酮不变式，以减少阿伯利亚p组？ 3。无限合并学的原则的证明理论强度是什么，例如，拉姆齐定理的变体，新的证明理论原则似乎最普遍？ 4。各种程度结构的代数结构是什么，通过相对可计算性编码整数的不可误解集？可计算性理论是数学逻辑研究在数学中的有效性的领域；可以将其视为试图桥接和阐明“古典”数学和“有效”数学之间的差距，因为前者越来越多地从算法转移到更抽象的“助理”观点。同时，计算理论将有效性与数学对象的效果进行比较，以形式的数学语言描述了如何在形式数学系统中证明了如何轻易的数学语句，这是数学逻辑总体的两个核心主题。 LEMPP建议研究这些概念的许多例子，尤其是来自现代代数（例如组和布尔代数）和组合学的概念。同时，LEMPP计划继续在学位理论中进行调查，研究可计算性和不可算置的相对概念，从而探索物理计算设备的理论局限性。