Mathematical Sciences: Logic and Computability

Shore Shore将研究可计算性理论（递归理论）和逻辑学的广泛主题。包括在第一个领域的研究是由计算的相对复杂性的不同概念排序的集合和函数的结构。特别强调的是那些有效可枚举的集合的复杂性结构，以及由不受限制的图灵机计算定义的相对可计算性的最一般概念。还将研究对访问oracle信息或计算运行时设置有效限制的计算过程。第二个领域包括研究可由有限自动机表示的结构，决策过程，非单调逻辑的分析和发展，并发编程模型，以及线性规划思想和算法在数据结构和逻辑编程中的应用。研究混合（连续和离散）控制理论的逻辑和数学基础，以及算法的实际实现。这个关于可计算性的研究项目主要是分析各种测量自然数（0,1,2，…）和其他常见数学结构上的函数复杂性的方法，根据它们的计算困难程度。主要目标是研究函数复杂性的各种概念之间的关系，这些概念是基于计算的机器模型和其他概念，例如定义或描述函数的困难程度。这里发展的技术也将应用于证明各种数学对象存在的难度的研究，以及对象存在的抽象证明与实际计算它的可能性或难度之间的关系。Shore的项目还包括对逻辑的应用，例如(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. ***