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.

该项目涉及可计算性理论领域的研究，包括整数集的经典可计算性理论，以及对其他数学领域的应用，特别是代数和逻辑。重点是问题的决定性的一阶理论的结构;有限子结构的表征;存在的非平凡自同构与可定义的属性;和分类的不可判定的问题代数。 可计算性理论早于现代计算机的存在，始于20世纪30年代Goedel的开创性工作。它研究了计算的理论界限（忽略对内存空间和运行时间的限制），从而为计算机科学中的许多应用提供了理论框架。经典的可计算性理论关注整数（被认为是许多数学领域的自然问题的编码），并试图根据它们的复杂性对整数集合进行分类。应用可计算性理论试图将这些方法应用于数学和计算机科学许多领域的自然问题。