Logic and Computability

提出的研究包括可计算性理论和逻辑的广泛主题，既有理论的，也有应用于数学和计算机科学的其他领域，也有一些可能的商业或工业应用。广义上讲，PI提出的主要研究方向是分析复杂性和相对复杂性。一个研究领域涉及自然数上的函数，然后是更广泛的一般数学结构。这项研究的主要衡量标准是图灵的相对可计算性概念，它抓住了我们通常的直觉，并对应于标准计算机器和程序语言的理想化版本的计算。提出的研究的另一个主要推力是针对数学定理和结构的复杂性的分析。在这里，人们将输入/假设的复杂性与结构/定理的输出/结论的复杂性进行比较。强度既可以通过计算来衡量，也可以根据证明构造的定理或正确性所需的公理来衡量。co-PI提议将逻辑领域的研究与计算机科学的应用结合起来，包括对非常简单的机器模型的研究，以及对验证计算机程序执行它们设计的任务而不是其他（可能是危险的）事情有用的逻辑语言。他还参与了普通（宏观）过程的量子控制方法的开发和专利申请。虽然这项工作受到了他之前支持的理论工作的影响，但它现在已经超出了本提案的范围。在更技术性的层面上，PI的建议涉及分析图灵度（计算的相对复杂性）和特别重要的子结构的结构。这里的重点是可定义性和不可定义性问题，以及相关结构中算术的（bi）解释。将特别强调与外部概念的关系，例如函数的增长率和函数或结构的算术或其他语言定义的复杂性。他的另一个主要研究方向是逆向数学。特别是对定理的分析，就其证明理论和计算强度而言，超出了所研究的标准系统的范围。因此，它表明有许多真正不同类型的构建原则，它们占据着不同的复杂程度，它们之间存在着复杂的关系。要研究的问题来自组合学、代数、模型理论和确定性领域。共同负责人的建议主要涉及自动机理论，特别是与控制理论相关的理论，以及用于捕获意识和信念概念的模态逻辑。

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.