Computability Theory, Facing Outwards

可计算性理论，面向外

• 批准号: 1362206
• 负责人: Russell Miller
• 金额: $ 11.23万
• 依托单位: CUNY Queens College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-15 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1362206&HistoricalAwards=false
• 关键词: Computability; Theory; Facing; Outwards

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.

在这个项目中，Pi Russell Miller将使用计算理论继续他的工作，以分析其他数学领域的问题的难度。 这些领域包括现场理论，交换和差异代数，模型理论和数理论，以及描述无数结构并有效研究它们的可能性。 传统的计算理论研究了数字计算机的功能以及可以使用此类计算机解决的问题的限制。 自艾伦·图灵（Alan Turing）开创性的工作以来，众​​所周知，运行任何程序的任何数字计算机都无法解决许多问题。 但是，即使这些“不合格”的问题也可以通过困难来排名：问题a比问题B更容易（或者至少不困难），如果我们可以展示如何解决B的B型计划也可以使我们也可以解决A。 实际上，在某些情况下，我们可以通过确定在此层次结构中确定相关的不合格问题位置来了解特定问题是否可以计算。 最近，PI做出了从解决方案到具体问题的贡献，都可以使用理性数字来确定某些多元方程式，再到有关解决代数差分方程的难度的更抽象问题，以及考虑从数学的不同领域中考虑结构的相对困难。要求使用一种算法来决定哪些二磷酸方程具有合理的解决方案。 他计划继续这项工作，考虑到密度0（即“非常接近”整数的“密度”）的特定问题。 在现场理论中，他通过询问和回答有关田间计算难度的自然可计算模型理论问题的实质性进步，以及通过使用计算性理论来回答有关田野与其他数学结构复杂性有关的复杂性的一般问题。他希望在差异代数中解决一个关键问题，该方案将帮助数学家更好地理解差异化的领域和差分方程的解决方案。 （这些类似于代数封闭的领域，但目前还不太了解。）几年来，他一直在为整个数学中的研究人员引入可计算性技术，并且经常能够对此类人的问题和方法感兴趣。 有了这笔赠款，这些努力肯定会继续下去。