Computability Theory, Facing Outwards

在这个项目中，PI Russell Miller将继续他的工作，使用可计算性理论来分析其他数学领域问题的难度。这些领域包括场论、交换和微分代数、模型论和数论，以及描述不可数结构和有效研究它们的可能性。传统的可计算性理论研究的是数字计算机的能力，以及使用这种计算机可以解决的问题的限制。自从阿兰·图灵的开创性工作以来，人们已经知道，任何一台运行任何程序的数字计算机都无法解决许多问题。然而，即使是这些“不可计算”的问题也可以根据难度进行排序：如果我们能够证明解决B的假设程序如何使我们也能解决A，那么问题A就比问题B更容易（或者至少不会更难）。事实上，在某些情况下，我们可以通过确定相关的不可计算问题在这个层次结构中的位置来了解特定问题是否可计算。最近，PI的贡献范围从确定某些多项式方程是否可以用有理数满足的具体问题的解决，到求解代数微分方程的难度以及考虑不同数学领域结构的相对难度等更抽象的问题。PI最近与几位数论学家合作，为希尔伯特有理数第十问题的不可判定性提供了新的证据，该问题要求一种算法来决定哪些丢芬图方程有有理数解。他计划继续这项工作，考虑密度为0的有理数的子问题（即“非常接近”整数）。在场论方面，他通过提出和回答关于计算场之间同构的困难的自然可计算模型理论问题，以及通过使用可计算性理论来回答有关场的复杂性与其他数学结构的复杂性的一般问题，取得了实质性的进展。他希望解决微分代数中的一个关键问题，其解决方案将帮助数学家更好地理解微分闭域和微分方程的解决方案。（这些类似于代数上的闭场，但目前还没有被很好地理解。）多年来，他一直带头向整个数学领域的研究人员介绍可计算性技术，并且经常能够引起这些人对他的问题和方法的兴趣。有了这笔赠款，这些努力肯定会继续下去。

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, commutative and differential algebra, model theory, and number theory, as well as the possibility of describing uncountable structures and studying them effectively. 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. Indeed, in certain cases we can learn whether a particular problem is computable or not by determining where related noncomputable problems sit in this hierarchy. Recently, the PI has made contributions ranging from solutions to concrete problems about deciding whether certain polynomial equations can be satisfied using rational numbers, to more abstract questions about the difficulty of solving algebraic differential equations and the relative difficulty of considering structures from different areas of mathematics.The PI recently collaborated with several number theorists to produce new evidence for the undecidability of Hilbert's Tenth Problem for the rational numbers, the problem which asks for an algorithm to decide which Diophantine equations have rational solutions. He plans to continue this work, considering the specific question of subrings of the rationals of density 0 (i.e., "very close" to the integers). In field theory, he has made substantial progress, both by asking and answering natural computable-model-theoretic questions about the difficulty of computing isomorphisms between fields, and also by using computability theory to answer general questions about the complexity of fields in relation to the complexity of other mathematical structures. He hopes to address a key question in differential algebra, whose solution would help mathematicians better understand differentially closed fields and solutions to differential equations. (These are analogous to algebraically closed fields, but are much less well understood at present.) For some years now he has taken the lead in introducing computability techniques to researchers throughout mathematics, and has often been able to interest such people in his questions and his methods. With this grant, those efforts will most certainly continue.