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 的项目涉及这些概念，包括他的专业领域、可计算性理论以及与其他领域的联系。 如上所述，算术中的可计算性根据自然数集的信息内容对它们进行分类。 伦普将研究保留该内容的变换的存在性，以及决定这些集合的某些基本属性的相关问题。 群论的目标是研究不可判定问题从无限到有限的转移。 伦普还将寻求“可行”可计算性的逻辑标准，也就是说可以由机器完成的计算类型。 ***