Computability Theory

Lempp提出了应用和纯计算理论的研究。 在前一个领域，Lempp提出研究不可数范畴一阶理论模型和布尔代数模型的计算复杂性。他还建议研究组合语句的证明理论强度，特别是Ramsey定理的变体，以找到弱二阶算术的新证明理论系统。在后者中，即，在纯可计算性理论中，Lempp计划通过研究它们的有限子结构，更好地理解三个重要的度结构，即可计算图灵度、Sigma^0_2-集的枚举度和可计算可计算集的差的图灵度，特别是有限格的可嵌入性和偏序嵌入到这些度结构中的扩展。可计算性理论是研究机器计算的理论局限性，不考虑内存空间或运行时间的限制。因此，在某种意义上，它是复杂性理论的理论表亲，复杂性理论是计算机科学的一个领域，研究给定时间或内存空间范围内的可计算性。可计算性理论中的典型结果表明，某些数学问题不能用任何计算机来解决，无论计算机有多快或多大。直到世纪末，数学本质上是算法：如果你解决了一个问题，你也可以给出一个有效的程序来找到解决方案。然而，在19世纪后期，人们发现许多数学证明可以做得更抽象，更优雅，以牺牲效率为代价。对这种方法的怀疑在20世纪30年代随着第一个不可判定性结果而出现，表明这种抽象往往导致“非算法解决方案”。Lempp的研究主要集中在代数和组合学中无法解决的问题的分析。这一领域的技术和成果不仅具有重要的理论意义，而且在计算机科学中具有实际应用价值。

Lempp proposes research in both applied and pure computabilitytheory. In the former area, Lempp proposes to investigate thecomputational complexity of models of uncountably categoricalfirst-order theories, and of Boolean algebras. He also propose tostudy the proof-theoretic strength of combinatorial statements,esp. variants of Ramsey's Theorem, in order to find newproof-theoretic systems of weak second-order arithmetic. In thelatter, i.e., in pure computability theory, Lempp plans to reacha better understanding of three important degree structures, thecomputably enumerable Turing degrees, the enumeration degrees ofthe Sigma^0_2-sets, and the Turing degrees of differences ofcomputably enumerable sets, by investigating their finitesubstructures, in particular the embeddability of finite latticesand extensions of embeddings of partial orders into these degreestructures.Computability theory is the study of the theoretical limitationsof computation by machines, irrespective of limitations of boundson memory space or run time. It is thus in some sense thetheoretical cousin of complexity theory, an area of computerscience studying computability within given time or memory spacebounds. Typical results in computability theory show that certainmathematical problems cannot be solved by any computer, no matterhow fast or how large. Up until the late 19th century,mathematics was essentially algorithmic: If you solved a problem,you could also give an effective procedure to find asolution. However, in the late 19th century, it turned out thatmany mathematical proofs could be done more abstractly and moreelegantly, at the expense of effectiveness. Suspicions about thisapproach came to the front in the 1930's with the firstundecidability results, showing that this abstraction often ledto "non-algorithmic solutions". Lempp's research focuses on theanalysis of unsolvable problems, mainly in algebra andcombinatorics. Techniques and results in this area are often notonly of great theoretical interest, but also have practicalapplications in computer science.