Computability Theory and its Applications

可计算性理论及其应用

• 批准号: 0600824
• 负责人: Antonio Montalban
• 金额: $ 8.77万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600824&HistoricalAwards=false
• 关键词: Computability; Theory; its; Applications

In this project, the P.I. studies problems in both pure andapplied Computability Theory. The problems in pure computabilitytheory are part of the ongoing program to understand the structure ofthe Turing Degrees. As for applied computability theory, the P.I.applies methods from computability theory to study the effectivecontent and proof-theoretical strength of various areas of bothclassical mathematics and foundations of mathematics. He concentratesin problems related to linear orderings, but not exclusively, and alsoworks in effective randomness and computable model theory. Computability Theory is the area of Logic that studies the notionof algorithm. Its applications are based on the idea that problemsthat can be solved using algorithms are simpler than the ones thatcannot. This is used in various ways to measure the complexity ofmathematical objects, theorems, sequences of zeros and ones, etc.. Itis usually the case that this analysis gives a better understanding ofthe subject under study.

在这个项目中，P.I.研究纯可计算性理论和应用可计算性理论中的问题。纯可计算性理论中的问题是正在进行的理解图灵度结构的计划的一部分。在应用可计算性理论方面，P.I.应用可计算性理论的方法来研究古典数学和数学基础的各个领域的有效内容和证明理论的强度。他专注于与线性排序相关的问题，但不限于此，还研究有效随机性和可计算模型理论。 可计算性理论是研究算法概念的逻辑学领域.它的应用是基于这样一种思想，即可以使用算法解决的问题比不能解决的问题更简单。这是用在各种方式来衡量数学对象的复杂性，定理，0和1的序列，等等。通常情况下，这种分析能使我们更好地理解所研究的主题.