Computability Theory

可计算性理论

• 批准号: 0140120
• 负责人: Steffen Lempp
• 金额: --
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-07-15 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0140120&HistoricalAwards=false
• 关键词: 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.

LEMPP提出了对应用和纯可计算理论的研究。 在前一种领域，LEMPP提议研究不可估量的一阶理论和布尔代数的模型模型的计算复杂性。他还提出了组合陈述的证明理论强度，尤其是。 Ramsey定理的变体是为了找到弱二阶算术的新预理论系统。在Thelatter中，即，在纯计算性理论中，LEMPP计划更好地理解三个重要学位结构，可师概述的Turing度，Sigma^0_2-sets的枚举度，以及通过重大约定的设置的差异程度有限核结构，特别是将部分订单嵌入到这些脱发中的有限晶格和扩展的嵌入性。可置性理论是对机器计算的理论局限性的研究，而与BOUNDSON MOMEMIT SPACE或运行时间的限制无关。因此，从某种意义上说，这是复杂性理论的表弟，这是计算机科学在给定时间或记忆空间内研究可计算性的领域。计算理论中的典型结果表明，无论快速变化或大小，任何计算机都无法解决某些数学问题。直到19世纪后期，数学本质上都是算法：如果您解决了问题，您也可以采用有效的程序来找到ASOLITY。然而，在19世纪后期，事实证明，可以更抽象，更高地进行数学证据，而以牺牲有效性为代价。关于这种诉求的怀疑是在1930年代的首次无法确定性的结果，表明该抽象通常导致“非算术解决方案”。 LEMPP的研究重点介绍了无法解决问题的研究，主要是在代数和康复者中。该领域的技术和结果通常具有很大的理论兴趣，但在计算机科学方面也具有实际应用。