Mathematical Sciences: Logic and Computability

数学科学：逻辑与可计算性

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

9503503 Shore Shore will investigate a broad range of topics in computability theory (recursion theory) and logic. 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 those 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 on the run-time of the computations will also be investigated. 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 study of the logical and mathematical foundations of hybrid (continuous and discrete) control theory will be conducted, as well as of the practical implementation of algorithms. This research project on computability is primarily concerned with analyzing various ways of measuring the complexity of functions on the natural numbers (0,1,2,...) and other common mathematical structures, in terms of how hard they are to compute. A primary goal is the study of the relations between various notions of complexity of a function, notions which are based on machine models of computation and other notions, such as how hard it is to define or describe the function. Techniques developed here will also be applied to the study of the difficulty of proving the existence of various mathematical objects, as well as to the relationship between abstract proofs of existence of an object and the possibility or difficulty of actually computing it. Shore's project also includes applications to logics such as (i) those designed to model the real life development of knowledge, taking into account the possibility that what we think we know today will seem false tomorrow, and (ii) ones designed to interact with real measuring devices to implement procedures to control systems that must both react to outside stimuli and follow logical decision procedures. ***

9503503 Shore Shore 将研究可计算性理论（递归理论）和逻辑方面的广泛主题。 第一个领域包括对按计算相对复杂性的不同概念排序的集合和函数的结构的研究。 将特别强调那些可有效枚举的集合的复杂性结构，以及由无限制的图灵机计算定义的相对可计算性的最一般概念。 还将研究对预言机信息的访问或计算的运行时间设置有效界限的计算程序。 第二个领域包括有限自动机表示的结构的研究、决策过程、非单调逻辑的分析和开发、并发编程模型以及线性编程思想和算法在数据结构和逻辑编程中的应用。 将研究混合（连续和离散）控制理论的逻辑和数学基础以及算法的实际实现。 这个关于可计算性的研究项目主要涉及分析测量自然数（0,1,2,...）和其他常见数学结构上的函数复杂性的各种方法，以及它们的计算难度。 主要目标是研究函数复杂性的各种概念、基于计算机器模型的概念和其他概念（例如定义或描述函数的难度）之间的关系。 这里开发的技术还将应用于研究证明各种数学对象存在的难度，以及对象存在的抽象证明与实际计算它的可能性或难度之间的关系。 肖尔的项目还包括逻辑应用，例如（i）那些旨在模拟现实生活中知识发展的逻辑，考虑到我们今天认为我们所知道的明天可能会显得错误的可能性，以及（ii）旨在与真实世界互动的逻辑。测量设备来实施程序来控制系统，这些系统必须对外部刺激做出反应并遵循逻辑决策程序。 ***