Mathematical Sciences: Computability, Decidability, and Definability

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

9504474 Lempp Lempp will investigate aspects of the central notions od computability, decidability, and definability in various parts of mathematics. Computability in arithmetic gives rise to degree structures, given by collections of sets of natural numbers of equal information content. Two related issues involved in this research are (i) the existence of automorphisms for such structures (yielding nondefinability results) and (ii) the decidability of fragments of their first-order theories. Computability in group theory involves the existence of algorithms for deciding certain properties of finitely presented groups. Lempp plans to determine the complexity of some of these problems in the Kleene-Mostowski hierarchy, and to show the undecidability of related problems for finite groups. Computability, decidability, and definability are central notions of mathematical logic, relevant to all of mathematics. Lempp's project deals with these notions, both inside his field of expertise, computability theory, and in the connections to other areas. As mentioned above, computability in arithmetic classifies sets of natural numbers according to their information content. Lempp will investigate the existence of transformations which preserve this content, and the related question of deciding certain elementary properties of these sets. In group theory the goal is to investigate the transfer of undecidable problems from the infinite to the finite. Lempp will also seek logical criteria for "feasible" computability, which is to say the sort of computations which could conceivably be done by machine. ***