Logic and Computability

Cornell University, Ithaca NY

Investigators

Abstract

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The research proposed centers on investigations of the structures of sets and functions ordered by relative complexity of computation. Particular emphasis will be placed on issues of definability and automorphisms. Also included in this area is the analysis of the relations between the difficulty of computing functions and other issues such as rates of growth, complexity of their definitions in arithmetic and the strength of axiom systems needed to prove their existence (reverse mathematics). The emphasis in reverse mathematics will be on analyzing basic combinatorial, model theoretic and set-theoretic principles that seem to lie outside the scope of the standard theories studied. In addition, a new approach to the issue of classifying the complexity of mathematical constructions based on computability theoretic notions will be developed. This approach should allow applications to uncountable and higher order structures that are either out of reach of current approaches or (as in the case of analysis on the real numbers) only handled through coding into countable structures. The proposed project includes research into a broad range of topics in computability theory and logic both theoretical and applied to other areas of mathematics and computer science. At the foundational level, this work will illuminate the nature of relative complexity of computation, the strength of axioms needed to prove standard mathematical theorems and the relations between these areas. In practical terms, results in this area (computable mathematics and model theory as well as reverse mathematics) 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 work related to automata theory and automatic structures is based on a very resource-limited model of computation that is often relevant to practical computing problems. The theoretical and foundational analysis of structures whose basic relations and functions are computable by such automata should also eventually be of practical significance. The primary focus in the most applied areas to be investigated 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. Here the issue is to understand how to mathematically model systems that include both digital (discrete) input and logical constraints as well as analog (continuous) information and constraints.