Computability Theory

可计算性理论是数理逻辑研究数学有效性的领域。它还研究了可计算性、可定义性和可证明性之间的密切联系，从而探讨了语言和证明在数学研究中的作用，这是整个逻辑的两个中心主题。经典可计算性理论研究整数集(被认为是编码自然数学问题)的信息含量，而应用可计算性理论研究主要来自代数和模型理论的构造可以在多大程度上有效地执行的问题。此外，可计算性理论提供了对数理逻辑其他部分的问题的见解，特别是在证明论和模型论中。Lempp建议特别研究以下几个方面：1.可计算性理论的方法能告诉我们关于不可数范畴理论公理化的量词界限的什么？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.