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海岸 海岸将调查广泛的可计算性理论（递归理论）和逻辑的主题。 第一个领域包括 研究集合和函数的结构， 计算的相对复杂性。 将特别强调 放置在这些集合的复杂性结构上， 可计算性，以及相对可计算性的最一般概念， 由不受限制的图灵机计算定义。 计算步骤 对访问Oracle信息或 还将研究计算的运行时间。 第二区域 包括研究结构表示的有限自动机，决策 过程，非单调逻辑的分析和发展，并发 编程模型，以及线性规划思想的应用， 算法到数据结构和逻辑编程。 逻辑的研究 混合（连续和离散）控制的数学基础 理论将进行，以及实际执行的 算法 这个关于可计算性的研究项目主要涉及分析各种测量函数复杂性的方法， 自然数（0，1，2，...）以及其他常见的数学结构， 计算的难度。 一个主要目标是研究 函数复杂度的各种概念之间的关系， 它基于计算机模型和其他概念，例如 定义或描述函数有多难。 开发的技术 这里也将适用于研究证明的困难， 各种数学对象的存在，以及它们之间的关系 一个对象存在的抽象证明和可能性之间的关系， 海岸的项目还包括 应用于逻辑，例如（i）设计用于模拟真实的生活的逻辑 知识的发展，考虑到我们今天认为我们知道的东西明天似乎是错误的可能性，以及（ii） 设计用于与真实的测量设备交互，以执行程序， 控制系统必须既对外界刺激作出反应，又遵循逻辑 决策程序。 ***