Mathematical Sciences: Computability, Decidability, and Definability

数学科学：可计算性、可判定性和可定义性

• 批准号: 9504474
• 负责人: Steffen Lempp
• 金额: $ 8.04万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9504474&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Computability; Decidability; 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. ***

9504474 Lempp Lempp将研究数学各个部分中的可计算性、可判断性和可定义性等核心概念的各个方面。算术中的可计算性导致了程度结构，这种结构由信息含量相等的自然数集合给出。本研究涉及的两个相关问题是(I)此类结构的自同构的存在性(产生不可定义性结果)和(Ii)其一阶理论片段的可判定性。在群论中，可计算性涉及决定有限表示群的某些性质的算法的存在性。Lempp计划在Kleene-Mostowski层次结构中确定其中一些问题的复杂性，并证明有限群的相关问题的不可判断性。可计算性、可判断性和可定义性是数理逻辑的核心概念，与所有数学相关。Lempp的项目涉及这些概念，在他的专业领域、可计算性理论以及与其他领域的联系中都是如此。如上所述，算术中的可计算性根据它们的信息内容对自然数集合进行分类。Lempp将研究保持这一内容的变换的存在性，以及确定这些集合的某些基本性质的相关问题。在群论中，目标是研究不可判定问题从无限空间到有限空间的转移。伦普还将为“可行的”可计算性寻找逻辑标准，也就是说，可以想象的那种可以由机器完成的计算。***