Recursion Theory and Its Applications

递归理论及其应用

• 批准号: 1266214
• 负责人: Mingzhong Cai
• 金额: $ 9.84万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-07-15 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1266214&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.

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