Logic and Computability

逻辑和可计算性

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

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. Included in the first area are investigations of the structures of sets and functions ordered by different notions of relative complexity of computation. Particular emphasis will be placed on the complexity structures of sets which are effectively enumerable and on the most general notion of relative computability as defined by unrestricted Turing machine computations. Computation procedures that place effective bounds on the access to oracle information or the run time of the computations will also be investigated, as well as reductions between real numbers based on the relative rates of convergence of effective approximations to the real numbers. Applications of the methods of pure computability theory will be made in the areas of computable algebra and model theory. The second area includes the study of structures representable by finite automata, decision procedures, the analysis and development of nonmonotonic logic, concurrent programming models, and applications of linear programming ideas and algorithms to data structures and logic programming. A primary focus here will be the logical and mathematical foundations of hybrid (continuous and discrete) control theory as well as the practical implementation of algorithms for these subjects based on the theoretical work being done.The work proposed in the first area is directed at a better understanding of the fundamental notions of computability and relative difficulty of computation for different tasks. The theoretical work deals both with the abstract notions of computability as well as with applications to specific branches of, and questions in, other areas of mathematics. One important application (within mathematics) concerns the general question of what starting information is needed to be able to compute other aspects of many important classes of mathematical structures. In practical terms, the results 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 second area deals more directly with developing the mathematical (and especially logical) tools needed for the crucial areas of program verification, data management, and automated control of real-world complex systems. Commercial applications are expected for some of this work and there has already been a spin off to a start-up company developing several applications including data compression and network management algorithms.

拟议的项目包括对可计算性理论（递归理论）和逻辑等广泛主题的研究，包括理论和数学和计算机科学其他领域的应用。第一个领域包括对按计算相对复杂性的不同概念排序的集合和函数的结构的研究。 将特别强调可有效枚举的集合的复杂性结构以及由不受限制的图灵机计算定义的相对可计算性的最一般概念。 还将研究对预言机信息的访问或计算的运行时间设置有效界限的计算程序，以及基于实数有效近似收敛的相对速率的实数之间的减少。纯可计算性理论方法的应用将在可计算代数和模型理论领域进行。第二个领域包括有限自动机表示的结构的研究、决策过程、非单调逻辑的分析和开发、并发编程模型以及线性编程思想和算法在数据结构和逻辑编程中的应用。这里的主要重点是混合（连续和离散）控制理论的逻辑和数学基础，以及基于正在完成的理论工作的这些主题的算法的实际实现。第一个领域提出的工作针对更好地理解可计算性的基本概念和不同任务的计算相对难度。理论工作既涉及可计算性的抽象概念，也涉及数学其他领域的特定分支和问题的应用。一个重要的应用（数学领域）涉及这样一个普遍问题：需要哪些起始信息才能计算许多重要数学结构类别的其他方面。实际上，结果有时表明没有适用于某些重要任务的算法，或者需要比预期更多的信息来编写计算所需结果的程序。第二个领域更直接地涉及开发程序验证、数据管理和现实复杂系统的自动控制等关键领域所需的数学（尤其是逻辑）工具。其中一些工作有望实现商业应用，并且已经分拆成立一家初创公司，开发多种应用程序，包括数据压缩和网络管理算法。