Computability Theory, Facing Outwards

在这个项目中，PI Russell Miller将继续他的工作，使用可计算性理论来分析其他数学领域问题的难度。这些领域包括场论、交换代数和微分代数；流形，拓扑的和分析的；不可数结构及其有效呈现和研究的可能性；实数的Blum-Shub-Smale可计算性和度理论。在场论方面，米勒已经取得了实质性的进展，他提出并回答了关于场的自然的可计算模型理论问题，并且注意到关于场的一般问题可以用可计算理论来回答。他率先向数理逻辑以外的研究人员介绍了可计算性技术，并且经常能够引起这些人对他的问题和方法的兴趣。领域也与他对不可数结构的兴趣相交：事实上，不可数领域非常自然地适合于局部可计算性的框架，这是米勒为考虑图灵计算模型中的不可数结构而开发的方法。在另一种研究不可数对象的方法中，卡尔弗特和米勒利用实数计算的Blum-Shub-Smale模型，提出了实数可计算流形的定义。他们发现，对于基本群的研究，BSS模型实际上已经消失了，而图灵计算模型是合适的。然而，考虑到流形上的距离，使用测地线或其他定义度量的方法，他们期望BSS计算或其他计算概念，例如来自可计算分析的概念，将是必不可少的。传统的可计算性理论研究的是数字计算机的能力，以及使用这种计算机可以解决的问题的限制。自从阿兰·图灵的开创性工作以来，人们已经知道，任何一台运行任何程序的数字计算机都无法解决许多问题。然而，即使是这些“不可计算”的问题也可以根据难度进行排序：如果我们能够证明解决B的假设程序如何使我们也能解决A，那么问题A就比问题B更容易（或者至少不会更难）。最近，PI Russell Miller对可计算模型理论做出了贡献，可计算模型理论是该领域的一个分支，研究涉及自然数和有理数的特定数学结构的不可计算问题。涉及所有实数的结构要大得多，因此更难以考虑，但Miller和许多其他人也引入了各种方法来解决这些结构。其中一些方法使用数字计算机，而另一些方法则对实数或其他结构进行精确运算。通过检查这些不同计算模型的极限，我们可以更好地理解精确的精确度提供了多少额外的能力，以及要解决哪些数学问题需要这样的精确度。

In this project, the PI Russell Miller will continue his work using computability theory to analyze the difficulty of problems in other areas of mathematics. These areas include field theory and commutative and differential algebra; manifolds, both topologically and analytically; uncountable structures and the possibility of presenting and studying them effectively; and Blum-Shub-Smale computability and degree theory for the real numbers. In field theory, Miller has already made substantial progress, both by asking and answering natural computable-model-theoretic questions about fields, and also by noticing general questions about fields which can be answered using computability theory. He has taken the lead in introducing computability techniques to researchers outside mathematical logic, and has often been able to interest such people in his questions and his methods. Fields also intersect with his interest in uncountable structures: indeed, uncountable fields fit very naturally into the framework of local computability, the approach developed by Miller for considering uncountable structures within the Turing model of computation. In another approach to uncountable objects, Calvert and Miller have developed a definition of real-computable manifold, using the Blum-Shub-Smale model of computation on the real numbers. They have found that for the study of the fundamental group, the BSS model actually melts away and the Turing model of computation is appropriate. However, for consideration of distances on manifolds, using geodesics or other ways of defining a metric, they expect that BSS computation or other notions of computation, such as those from computable analysis, will be essential.Traditional computability theory examines the capabilities of digital computers and the limits on the problems which can be solved using such computers. Since the pioneering work of Alan Turing, it has been known that many problems cannot be solved by any digital computer running any program whatsoever. Even these "noncomputable" problems can be ranked by difficulty, however: problem A is easier (or at least, no more difficult) than problem B if we can show how a hypothetical program solving B would allow us to solve A as well. Recently, the PI Russell Miller has made contributions to computable model theory, the branch of this field in which one studies noncomputable problems about specific mathematical structures involving the natural numbers and the rational numbers. Structures involving all real numbers are much larger and therefore trickier to consider, but Miller and many others have introduced various methods for addressing these structures as well. Some of these methods use digital computers, while others assume exact-precision arithmetic on the real numbers or other structures. By examining the limits of these different models of computation, we can understand better how much extra power is provided by exact precision, and which mathematical problems require such precision if they are to be solved.