Logic and Computability

逻辑和可计算性

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

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The research proposed centers on investigations of the structures of sets andfunctions ordered by relative complexity of computation. Particular emphasiswill be placed on issues of definability and automorphisms. Also included inthis area is the analysis of the relations between the difficulty of computingfunctions and other issues such as rates of growth, complexity of theirdefinitions in arithmetic and the strength of axiom systems needed to provetheir existence (reverse mathematics). The emphasis in reverse mathematicswill be on analyzing basic combinatorial, model theoretic and set-theoreticprinciples that seem to lie outside the scope of the standard theoriesstudied. In addition, a new approach to the issue of classifying thecomplexity of mathematical constructions based on computability theoreticnotions will be developed. This approach should allow applications touncountable and higher order structures that are either out of reach ofcurrent approaches or (as in the case of analysis on the real numbers) onlyhandled through coding into countable structures.The proposed project includes research into a broad range of topics incomputability theory and logic both theoretical and applied to other areas ofmathematics and computer science. At the foundational level, this work willilluminate the nature of relative complexity of computation, the strength ofaxioms needed to prove standard mathematical theorems and the relationsbetween these areas. In practical terms, results in this area (computablemathematics and model theory as well as reverse mathematics) at times indicatethat there are no algorithms for certain important tasks or that moreinformation than might have been expected is needed to write programscalculating the desired results. The work related to automata theory andautomatic structures is based on a very resource-limited model of computationthat is often relevant to practical computing problems. The theoretical andfoundational analysis of structures whose basic relations and functions arecomputable by such automata should also eventually be of practicalsignificance. The primary focus in the most applied areas to be investigatedwill be the logical and mathematical foundations of hybrid (continuous anddiscrete) control theory as well as the practical implementation of algorithmsfor these subjects based on the theoretical work being done. Here the issue isto understand how to mathematically model systems that include both digital(discrete) input and logical constraints as well as analog (continuous)information and constraints.

该奖项是根据2009年的《美国回收与再投资法》（公法111-5）资助的。拟议的研究集中在对计算相对复杂性订购的集合和函数结构的调查中心。特别强调的是确定性和自动形态的问题。在这个领域中还包括分析计算功能的难度与其他问题（例如生长速率，其算术中定义的复杂性以及证明存在所需的公理系统的强度）之间的关系（反向数学）。反向数学的重点将是分析基本组合，模型理论和固定理论原理，这些理论和理论原理似乎不在标准理论范围的范围之内。此外，将开发一种基于可计算性理论调查的数学构建体分类的新方法。这种方法应允许应用程序和高阶结构，这些结构要么是无法触及的方法，要么（如对实数的分析）仅通过编码为可数的结构。拟议的项目包括针对广泛的主题性能的研究理论和逻辑理论和逻辑都应用于其他数学和计算机科学领域。在基础层面上，这项工作将阐明计算相对复杂性的性质，即证明标准数学定理和这些领域之间的关系所需的强度。实际上，在该领域（计算机手术和模型理论以及反向数学）中的结果有时表明，对于某些重要任务没有算法，或者需要比预期的更大的信息来编写程序范围，以划定所需的结果。与自动机理论和自动结构相关的工作是基于非常有限的计算模型，通常与实践计算问题有关。对这种自动机可兼容的基本关系和功能的结构的理论和基础分析最终也应具有实践意义。在大多数应用领域中，要研究的领域的主要重点是混合（连续和discrete）控制理论的逻辑和数学基础，以及基于所做的理论工作的这些主题的算法实施。在这里，问题是要了解如何对包括数字（离散）输入和逻辑约束以及模拟（连续）信息和约束的数学建模系统进行建模。