Recursion Theory and Its Applications

递归理论及其应用

• 批准号: 1458061
• 负责人: Rosa Orellana
• 金额: $ 5.52万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1458061&HistoricalAwards=false
• 关键词: Recursion; Theory; Its; Applications

In the proposed project, Cai plans to study classical recursion theory with emphasis on some interesting long-standing questions. In addition, he hopes to introduce new ideas and concepts to enrich the field, as well as to investigate some recent new results for different approaches and potential improvements. Cai also aims to expand the scope to applications of recursion theory, in particular he will continue the study of the degrees of provability, where proof-theoretic results can be proved using recursion-theoretic methods such as diagonalization and the recursion theorem.Recursion theory is a field of logic addressing effective content of mathematical practices (e.g., which of the mathematical procedures can be performed by automated machines, or computers). It has classical applications explaining why some mathematical problems (e.g., Hilbert's Tenth Problem) are theoretically unsolvable. The proposed project aims to improve the understanding of recursion theory by investigating old and new open problems, as well as to expand it by building connections to other fields such as proof theory. The proposed project has potential applications explaining how certain arithmetical facts could be theoretically unprovable.

在这个项目中，Cai计划研究经典递归理论，重点是一些有趣的长期存在的问题。此外，他希望引入新的想法和概念来丰富该领域，并调查最近的一些新结果，以获得不同的方法和潜在的改进。蔡还旨在扩大递归理论的应用范围，特别是他将继续研究可证明性的程度，其中证明理论的结果可以使用递归理论方法来证明，如对角化和递归定理。递归理论是一个逻辑领域，解决数学实践的有效内容（例如，这些数学过程中的哪一个可以由自动化机器或计算机执行）。它有经典的应用解释为什么一些数学问题（例如，希尔伯特第十问题（Hilbert's Tenth Problem）在理论上是无法解决的。该项目旨在通过调查新旧开放问题来提高对递归理论的理解，并通过与其他领域（如证明理论）建立联系来扩展递归理论。拟议的项目具有潜在的应用，可以解释某些算术事实如何在理论上无法证明。