Computability Theory

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

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.