Computability, Enumerability, Decidability and Definability

可计算性、可枚举性、可判定性和可定义性

• 批准号: 9732526
• 负责人: Steffen Lempp
• 金额: $ 9.66万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-01 至 2002-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9732526&HistoricalAwards=false
• 关键词: Computability; Enumerability; Decidability; Definability

This project involves research in the area of computability theory, both classical computability theory on the set of integers, and applications to other fields of mathematics, in particular algebra and logic. The focus is on questions of decidability of the first-order theory of structures; the characterization of finite substructures; the existence of nontrivial automorphisms versus definable properties; and the classification of undecidable problems in algebra. Computability theory predates the existence of modern computers, starting with the ground-breaking work of Goedel in the 1930's. It investigates the theoretical bounds of computation (neglecting restrictions on memory space and run time), thus providing the theoretical framework for many applications in computer science. Classical computability theory focuses on the integers (thought of as coding natural problems from many areas of mathematics) and tries to classify sets of integers by their complexity. Applied computability theory tries to apply these methods to natural problems in many areas of mathematics and computer science.

该项目涉及在可计算理论领域的研究，包括整数集的经典可计算理论，以及对其他数学领域的应用，尤其是代数和逻辑。重点是结构一阶理论的可决定性问题。有限子结构的表征；非平凡的自动形态与可确定特性的存在；以及代数中不可确定的问题的分类。 计算理论早于现代计算机的存在，从1930年代的戈德尔（Goedel）的开创性工作开始。它研究了计算的理论界限（忽略了对记忆空间的限制和运行时间），从而为计算机科学中的许多应用提供了理论框架。古典计算理论的重点是整数（认为是数学许多领域的自然问题），并试图通过其复杂性对整数进行分类。应用的计算理论试图将这些方法应用于数学和计算机科学许多领域的自然问题。