Logic and Computability

点击翻译按钮获取中文摘要

The proposed project includes research into a broad range of topics in computability theory (recursion theory) and logic, both theoretical and applied to other areas of mathematics and computer science. 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 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 the run time of the computations will also be investigated, as well as reductions between real numbers based on the relative rates of convergence of effective approximations to the real numbers. Applications of the methods of pure computability theory will be made in the areas of computable algebra and model theory. 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 primary focus here will be the logical and mathematical foundations of hybrid (continuous and discrete) control theory as well as the practical implementation of algorithms for these subjects based on the theoretical work being done.The work proposed in the first area is directed at a better understanding of the fundamental notions of computability and relative difficulty of computation for different tasks. The theoretical work deals both with the abstract notions of computability as well as with applications to specific branches of, and questions in, other areas of mathematics. One important application (within mathematics) concerns the general question of what starting information is needed to be able to compute other aspects of many important classes of mathematical structures. In practical terms, the results at times indicate that there are no algorithms for certain important tasks or that more information than might have been expected is needed to write programs calculating the desired results. The second area deals more directly with developing the mathematical (and especially logical) tools needed for the crucial areas of program verification, data management, and automated control of real-world complex systems. Commercial applications are expected for some of this work and there has already been a spin off to a start-up company developing several applications including data compression and network management algorithms.