Logic and Computability

逻辑和可计算性

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

The research proposed includes a broad range of topics in computability theory and logic both theoretical and applied to other areas of mathematics and computer science with some possible commercial or industrial applications as well. Broadly speaking, the major research proposed by the PI is directed at analyzing complexity and relative complexity. One area of study concerns functions on the natural numbers and then more broadly general mathematical structures. The primary measuring rod for this investigation is Turing's notion of relative computability which captures our usual intuitions and corresponds to computations by idealized versions of standard computing machines and program languages. The other major thrust of the proposed research is directed at an analysis of the complexity of mathematical theorems and constructions. Here, one compares the complexity of the inputs/hypotheses to that of the outputs/conclusions of the constructions/theorems. Strength is measured both computationally and in terms of the axioms needed to prove the theorem or correctness of the construction. The co-PI has proposed directing research in areas of logic with applications to computer science including the study of very simple machine models as well as logical languages useful for verifying that computer programs do what they are designed to do and not other (perhaps dangerous) things. He is also involved in developing and patenting methods for quantum control of ordinary (macro)processes. While this work has been influenced by his previously supported theoretical work, it now lies outside the scope of this proposal.At a more technical level, the PI's proposals deal with analyzing the structure of the Turing degrees (of relative complexity of computation) and of particularly important substructures. The emphasis here is on questions of definability and nondefinability as well as (bi)interpretations of arithmetic in the relevant structures. Particular emphasis will be placed on relations to external notions such as rates of growth for functions and the complexity of the definitions in arithmetic or other languages of the functions or structures. His other major focus is on reverse mathematics. In particular, the analysis of theorems that, in terms of their proof theoretic and computational strength, lie outside the scope of the standard systems studied. Thus it demonstrates that there are many truly distinct types of construction principles occupying different levels of complexity with involved relations among them. Problems to be studied come from the realms of combinatorics, algebra, model theory and determinacy. The co-PI's proposals primarily deal with automata theory, particularly as related to control theory, and modal logics used to capture notions of awareness and belief.

拟议的研究包括计算理论和逻辑上的广泛主题，并应用于其他可能的商业或工业应用，并应用于其他数学和计算机科学领域。从广义上讲，PI提出的主要研究旨在分析复杂性和相对复杂性。一个研究领域涉及自然数，然后是更广泛的一般数学结构。该调查的主要测量杆是图灵的相对可计算性概念，该概念捕获了我们通常的直觉，并与标准计算机和程序语言的理想化版本相对应。拟议研究的另一个主要力量是针对数学定理和构造的复杂性的分析。在这里，将输入/假设的复杂性与构造/定理的输出/结论的复杂性进行了比较。在计算和证明构造的正确性所需的公理方面，都可以测量强度。 Co-Pi提出了指导逻辑领域的研究，其中包括计算机科学的应用，包括对非常简单的机器模型的研究以及逻辑语言，可用于验证计算机程序是否执行他们设计的工作，而不是其他（也许是危险）事物。他还参与开发和专利方法，以控制普通（宏）过程。尽管这项工作受到他先前支持的理论工作的影响，但现在它不在该提案的范围之内。在更具技术性的层面上，PI的建议涉及分析图灵学位（计算相对复杂性）和的结构。特别重要的子结构。这里的重点是相关结构中算术的确定性和非可用性以及（BI）解释的问题。特别重点将放在与外部概念的关系上，例如功能的增长率以及功能或结构的其他语言中定义的复杂性。他的另一个主要重点是逆向数学。特别是，就其证明理论和计算强度而言，对定理的分析不在研究的标准系统的范围之外。因此，它表明，有许多真正不同类型的构建原则占据了不同水平的复杂性，其中涉及的关系。要研究的问题来自组合学，代数，模型理论和决定性的领域。 Co-Pi的建议主要涉及自动机理论，尤其是与控制理论相关，以及用于捕捉意识和信念概念的模态逻辑。