Logic is the language of mathematics and computer science and also provides the foundation for these areas. Logic is used in expert systems in medicine and also in hybrid algorithms for software design My recent work in mathematical logic has focused on the notions of computability, complexity and randomness, along with application to other areas of mathematics, including analysis, algebra, and combinatorics.
The largest organization for researchers in logic is the Association for Symbolic Logic
The largest organization for research in computability is Computability in Europe
The Computability and Complexity in Analysis Network is another active research group.
Effectively Closed Sets BOOK DRAFT
Effectively closed sets, or \(\Pi^0_1\) classes, are a unifying theme in the study of computability and its applications and are also central to the study of algorithmic randomness. The basic idea here is to view the solution of a problem, such as coloring a graph, as a sequence of choices, or branches, so that the solution set corresponds to a tree. We are interested in how to represent mathematical problems in terms of these trees and in how the complexity of the tree relates to the complexity of the problem. The set of paths through a computable tree is an effectively closed set. Other examples include the set of fixed points of a computable real function and the set of stable models of a logic program. This enables one to construct, for example, a computable graph which has a 3-coloring but has no computable 3-coloring. The complexity of solving a problem may be specified by means of index sets. For example, the problem of determining whether a computable tree has a computable path is \(\Sigma^0_3\)complete, that is, it requires three quantifiers to define.
The rich structure of the family of effectively closed sets can be seen under two partial orderings. The degrees of difficulty are given by saying that class A is not more difficult than class B if any member of B may be used to compute a member of A. Problems of definability and automorphism are studied in the lattice of inclusion. For example, the property of finiteness is preserved under automorphism and was shown to be definable in the lattice.
Algorithmic Randomness
The basic problem of algorithmic randomness has been to quantify the randomness of a single real number. The notion of randomness was defined by Kolmogorov in terms of information content and by Martin-Lof in terms of probability. Our research was supported by a National Science Foundation Focused Research Group award of over \$500,000, in collaboration with several other universities. Cenzer and his collaborators have developed notions of Algorithmic Randomness of Closed Sets and of continuous functions. Every random closed set is perfect, has measure zero and has Hausdorff dimension log (4/3). Random continuous functions map computable reals to random reals and the set of zeroes of a random function is a random closed set. We also examine Algorithmic Capacity . We are currently working on complexity versions of randomness
in Subcomputable bounded pseudorandomness .
Computable Analysis
The main theme of computable analysis is the study of effective aspects of real and complex numbers and functions. Index sets for effectively closed sets of reals and for computable real functions are developed and used to analyze the computability of cardinality and measure and also the complexity of certain differential equations in Index Sets for Computable Differential Equations . Complexity theory for analysis leads to the result that the famous P=NP problem is equivalent to whether every NP closed set of reals is also polynomial time closed. Recent papers, including
Computability of Countable Subshifts in One Dimension, have investigated computable subshifts and the connection with effective symbolic dynamics.
Computable algebra and model theory
This area examines the effective content of results from algebra and model theory. One new result is a complexity-theoretic version of the classic result that every decidable theory has a computable model. A model A is computably categorical if any other model isomorphic to A is in fact computably isomorphic to A. Recent work extends this notion to arithmetically definable models and isomorphism and in particular to definability in the difference hierarchy over the computably enumerable sets. Structures studied include equivalence relations and Abelian groups. Complexity Theoretic Model Theory and Algebra examines structures with functions and relations computable in, say, polynomial time. Current work examines so-called automatic structures, where the relations are recognizable by finite automata and the functions are computable by finite transducers. This research has been supported by a series of NSF Collaboration grants.
Logic Programming
Logic programming is a paradigm for automated deduction. It is part of artificial intelligence since it provides a tool for machine learning and reasoning. Logic programming is applied to databases in medical diagnosis, air traffic analysis and other areas. Our work in papers, such as
Logic Programming with Infinite Sets , concerns the complexity of reasoning with logic programs.