Logic and Computability

逻辑和可计算性

• 批准号: 0554855
• 负责人: Richard Shore
• 金额: $ 21万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2010-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0554855&HistoricalAwards=false
• 关键词: Logic; Computability

The research proposed centers on investigations of the structures of sets and functions ordered by relative complexity of computation. Particular emphasis will be placed on issues of definability and automorphisms. Also included in this area is the analysis of the relations between the difficulty of computing functions and other issues such as rates of growth, complexity of their definitions in arithmetic and the strength of axiom systems needed to prove their existence (reverse mathematics). The emphasis in reverse mathematics will be on analyzing basic combinatorial principles that seem to lie outside the scope of the standard theories studied. Applications of the methods of pure computability theory will be made in the areas of model theory and notions used in differential geometry. The emphasis in computable model theory will be on the ways in which choosing different representations of a given structure affect the computational complexity of various relations or procedures on the elements of the structure. Issues in automata theory and especially automatic structures that deal with computable complexity will also be addressed.The proposed project includes research into a broad range of topics in computability theory (recursion theory) and logic both theoretical and applied to other areas of mathematics and computer science. At the foundational level, this work illuminates the nature of relative complexity of computation, the strength of axioms needed to prove standard mathematical theorems and the relations between these areas. In practical terms, results in this area (computable mathematics and model theory as well as reverse mathematics) at times indicate that there are no algorithms for certain important tasks or that more information than might have been expected is needed to write programs calculating the desired results. The work related to automata theory and automatic structures is based on a very limited model of computation that is often relevant to practical computing problems. The theoretical and foundational analysis of structures whose basic relations and functions are computable by such automata should also eventually be of practical significance.

该研究提出的重点是研究按计算的相对复杂性排序的集合和函数的结构。将特别强调可定义性和自同构的问题。该领域还包括分析计算函数的难度与其他问题之间的关系，例如增长率、算术定义的复杂性以及证明其存在所需的公理系统的强度（逆向数学）。逆向数学的重点是分析基本组合原理，这些原理似乎超出了标准理论研究的范围。纯可计算性理论方法的应用将在模型理论和微分几何中使用的概念领域进行。可计算模型理论的重点将放在选择给定结构的不同表示方式影响结构元素上的各种关系或过程的计算复杂性的方式。自动机理论的问题，特别是处理可计算复杂性的自动结构的问题也将得到解决。拟议的项目包括对可计算性理论（递归理论）和逻辑理论以及应用于数学和计算机科学其他领域的广泛主题的研究。在基础层面上，这项工作阐明了计算相对复杂性的本质、证明标准数学定理所需的公理的强度以及这些领域之间的关系。实际上，该领域（可计算数学和模型理论以及逆向数学）的结果有时表明，对于某些重要任务没有算法，或者需要比预期更多的信息来编写计算所需结果的程序。与自动机理论和自动结构相关的工作基于非常有限的计算模型，该模型通常与实际计算问题相关。其基本关系和功能可由此类自动机计算的结构的理论和基础分析最终也应该具有实际意义。