Computability Theory and its Applications

直到19世纪中期左右，数学主要是算法。存在的证明通常是通过给出物体的实际构造来完成的。随着数学变得越来越抽象，人们开始研究算法和可计算性的概念。第一个障碍是对算法或可计算的定义。当面对一种算法时，人们会同意它是一种算法，但人们如何证明某些东西不能被计算出来，或者不能被算法解决呢？到了20世纪30年代，图灵和其他人的工作在可计算性的概念上达到了顶峰。******自20世纪30年代以来，可计算性理论的发展已经远远超出了仅仅检查什么是可计算的，什么是不可计算的。我们有相对可计算性的概念，我们说A是从B计算出来的，如果有一些程序可以计算A，如果它被允许引用（有限经常）无限磁带编码B。******在这个项目中，我建议研究数学的各个领域，并使用可计算性理论来检查证明的复杂性。这有助于回答诸如证明一件事与另一件事相比有多难这样的问题。原始证明是最有效的吗？分辨相似的物体实际上是相似的有多难？通过研究这些性质，我们可以发现正在研究的数学领域的有趣现象，通常会导致进一步的见解。

Up to the mid 19th century or so, mathematics was mostly algorithmic. Proofs of existence were usually done by giving an actual construction of the object. As mathematics began to become more abstract, people began to study the notions of algorithms and computability. The first stumbling block was on the definition of what it meant to be algorithmic or computable. When faced with an algorithm, people would agree that it was one, but how would one show that something could not be computed, or solved by an algorithm? By the 1930s, work of Turing and others culminated in an acceptable notion of computability.******Since the 1930s, computability theory has developed far beyond just checking what is computable and what is not. We have notions of relative computability, where we say A is computed from B if there is some program that can compute A if it is allowed to refer (finitely often) to an infinite tape coding B.******In this project, I propose to study various areas of mathematics, and use computability theory to examine the complexity of the proofs. This can help answer questions such as how difficult is it to prove one thing compared to another? Is the original proof the most efficient? How difficult is it to tell that similar objects are actually similar? By studying these properties, we can discover interesting phenomena about the area of mathematics being studied, often leading to further insight.