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