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将调查的可计算性，可判定性和可定义性的中心概念的各个方面， 数学 算术中的可计算性产生了程度 结构，由相等信息量的自然数集合给出。 本研究涉及的两个相关问题是（i） 这种结构的自同构的存在性（产生 （二）不确定性的结果）和（二）其片段的可判定性 一阶理论 群论中的可计算性涉及到判定群的某些性质的算法的存在。 Lempp计划确定其中一些问题的复杂性， Kleene-Mostowski层次，并显示相关的不可判定性 有限群的问题。 可计算性、可判定性和可定义性是数理逻辑的核心概念，与所有数学相关。 伦普 项目涉及这些概念，无论是在他的专业领域，可计算性理论，并在连接到其他领域。 如所提及 上面，算术中的可计算性根据它们的信息内容对自然数集合进行分类。 Lempp会调查的 存在的变换保持这一内容，以及相关的问题，决定某些基本性质的这些集。 在群论中，目标是研究不可判定的 从无限到有限的问题。 Lempp还将寻求逻辑 “可行”可计算性的标准，也就是说， 可以想象的是机器可以完成的计算。 ***