Mathematical Sciences: Logic and Computability

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

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. ***