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.

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