Computable Stability Theory

可计算稳定性理论

• 批准号: 1201338
• 负责人: Uri Andrews
• 金额: $ 10.5万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-06-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1201338&HistoricalAwards=false
• 关键词: Computable; Stability; Theory

Andrews proposes a program of research spanning classical computability theory, classical model theory, and especially the interplay between computability theory and model theory. More specifically, the proposed research will develop the emerging field of Computable Stability Theory, where the methods of stability theory plays a key role is the study of effective properties of first order theories. Stability theory is the part of model theory which focuses on the underlying geometrical or structural nature of the mathematical objects. Generally speaking, the more underlying structure the mathematical object respects, the easier it is to compute information about the object. This forms a back-and-forth relationship between stability and computability, and this interplay is the focus of Computable Stability Theory. Questions arising from Computable Stability Theory lead to new questions in classical model theory as well as computability, which sheds light on both subjects. Among these questions is when quantifier elimination to some level can be derived from geometrical properties.Computable Stability Theory endeavors to explore the basic statement that "structurally simple objects ought to be easier to compute." Model theory, a branch of mathematical logic, offers tools to analyze structural simplicity by studying objects in the context of their first order language. The understanding of the language associated to an object or class of objects can often be translated to a deeper understanding of the objects themselves. Computability theory studies questions of computation and relative computation with regard to mathematical objects. By combining tools from both fields, Andrews will examine the question of when structural simplicity does and when it does not translate into computational simplicity.

安德鲁斯提出了一个涵盖经典可计算性理论、经典模型理论，特别是可计算性理论和模型理论之间相互作用的研究计划。更具体地说，所提出的研究将发展可计算稳定性理论的新兴领域，其中稳定性理论方法在研究一阶理论的有效性质方面发挥着关键作用。稳定性理论是模型理论的一部分，专注于数学对象的基本几何或结构性质。一般来说，数学对象遵循的底层结构越多，计算有关该对象的信息就越容易。这在稳定性和可计算性之间形成了一种往复的关系，这种相互作用是可计算稳定性理论的焦点。可计算稳定性理论提出的问题引发了经典模型理论和可计算性中的新问题，这为这两个主题提供了线索。这些问题之一是何时可以从几何属性导出某种程度的量词消除。可计算稳定性理论致力于探索“结构简单的对象应该更容易计算”的基本陈述。模型论是数理逻辑的一个分支，它提供了通过在一阶语言背景下研究对象来分析结构简单性的工具。对与一个对象或一类对象相关联的语言的理解通常可以转化为对对象本身的更深入的理解。可计算性理论研究关于数学对象的计算和相关计算问题。通过结合这两个领域的工具，安德鲁斯将研究结构简单性何时会转化为计算简单性何时不会转化为计算简单性的问题。