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