Abstract

This thesis examines the prospects for mechanical procedures that can identify true, complete, universal, first-order logical theories on the basis of a complete enumeration of true atomic sentences. A sense of identification is defined that is more general than those which are usually studied in the learning theoretic and inductive inference literature. Some identification algorithms based on confirmation relations familiar in the philosophy of science are presented. Each of these algorithms is shown to identify all purely universal theories without function symbols. It is demonstrated that no procedure can solve this universal theory inference problem in the more usual senses of identification. The question of efficiency for theory inference systems is addressed, and some definitions of limiting complexity are examined. It is shown that several aspects of obvious strategies for solving the universal theory inference problem are NP-hard. Finally, some non-worst case heuristic search strategies are examined in light of these NP-completeness results. These strategies are based upon an isomorphism between clausal entailments of a certain class and partition lattices, and are applicable to the improvement of earlier work on language acquisition and logical inductive inference