Computability Theory

点击翻译按钮获取中文摘要

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.