Logic and Computability

Cornell University, Ithaca NY

Investigators

Abstract

The research proposed includes a broad range of topics in computability theory and logic both theoretical and applied to other areas of mathematics and computer science with some possible commercial or industrial applications as well. Broadly speaking, the major research proposed by the PI is directed at analyzing complexity and relative complexity. One area of study concerns functions on the natural numbers and then more broadly general mathematical structures. The primary measuring rod for this investigation is Turing's notion of relative computability which captures our usual intuitions and corresponds to computations by idealized versions of standard computing machines and program languages. The other major thrust of the proposed research is directed at an analysis of the complexity of mathematical theorems and constructions. Here, one compares the complexity of the inputs/hypotheses to that of the outputs/conclusions of the constructions/theorems. Strength is measured both computationally and in terms of the axioms needed to prove the theorem or correctness of the construction. The co-PI has proposed directing research in areas of logic with applications to computer science including the study of very simple machine models as well as logical languages useful for verifying that computer programs do what they are designed to do and not other (perhaps dangerous) things. He is also involved in developing and patenting methods for quantum control of ordinary (macro)processes. While this work has been influenced by his previously supported theoretical work, it now lies outside the scope of this proposal. At a more technical level, the PI's proposals deal with analyzing the structure of the Turing degrees (of relative complexity of computation) and of particularly important substructures. The emphasis here is on questions of definability and nondefinability as well as (bi)interpretations of arithmetic in the relevant structures. Particular emphasis will be placed on relations to external notions such as rates of growth for functions and the complexity of the definitions in arithmetic or other languages of the functions or structures. His other major focus is on reverse mathematics. In particular, the analysis of theorems that, in terms of their proof theoretic and computational strength, lie outside the scope of the standard systems studied. Thus it demonstrates that there are many truly distinct types of construction principles occupying different levels of complexity with involved relations among them. Problems to be studied come from the realms of combinatorics, algebra, model theory and determinacy. The co-PI's proposals primarily deal with automata theory, particularly as related to control theory, and modal logics used to capture notions of awareness and belief.