Computability Theory, Facing Outwards

可计算性理论，面向外

• 批准号: 1001306
• 负责人: Russell Miller
• 金额: $ 10.72万
• 依托单位: CUNY Queens College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1001306&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 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.

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