Computability and Mathematical Definability

可计算性和数学可定义性

• 批准号: 1001551
• 负责人: Theodore Slaman
• 金额: $ 30万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1001551&HistoricalAwards=false
• 关键词: Computability; Mathematical; Definability

Slaman proposes to investigate the effective, and more generally definable, aspects of mathematical phenomena such as genericity, compactness, and randomness. One central question in this investigation is to give necessary and suffcient conditions on an infinite binary sequence X which ensure that there is a continuous measure m such that X is effectively or arithmetically random relative to m. This is a classic mathematical problem, given an individual data set determine a distribution which would generate it. By results of Reimann and Slaman, for all but countably many X there is such an m. The argument is highly meta-mathematical. Necessarily so, as Reimann and Slaman have also shown that this co-countability theorem cannot be proven without invoking infinitely many iterations of the power set of the reals. In the emerging picture, there is a close interaction between a sequence's failure to have a random ingredient and it's being structurally definable, which should be studied more deeply.Slaman's proposal can be viewed in the context of the continuing investigation of computability and mathematical definability. With quantitative mathematical analysis of these phenomena, one can answer questions of the form ``Is there an algorithm to solve all problems of a this type?'', ``Is there a simple example with specific properties'', ``Is there a concrete classification of all structures with these properties?''. One can also address questions of the sort ``Are these techniques adequate to resolve this question?'' or ``How random must a sequence be in order to exhibit a particular typical behavior?'' One must develop a detailed theory of computation to show that there is no algorithm of a certain type. Similarly, one must develop a detailed theory of definability to show that there is no simple example with certain properties or to show that certain phenomena do not have concrete classifications.

斯拉曼提议研究数学现象的有效且更普遍可定义的方面，例如通用性、紧凑性和随机性。 这项研究的一个核心问题是给出无限二元序列 X 的必要和充分条件，以确保存在连续测度 m，使得 X 相对于 m 是有效或算术随机的。 这是一个经典的数学问题，给定一个单独的数据集确定生成它的分布。 根据 Reimann 和 Slaman 的结果，除了可数多个 X 之外，所有 X 都存在这样一个 m。这个论证是高度元数学的。必然如此，正如赖曼和斯拉曼也表明的那样，如果不调用实数幂集的无限多次迭代，就无法证明这个可数性定理。在正在出现的情况中，序列不具有随机成分与其在结构上可定义之间存在密切的相互作用，这应该进行更深入的研究。斯拉曼的提议可以在可计算性和数学可定义性的持续研究的背景下看待。通过对这些现象进行定量数学分析，人们可以回答以下形式的问题：“是否有一种算法可以解决这种类型的所有问题？”，“是否有一个具有特定属性的简单示例”，“是否有具有这些属性的所有结构的具体分类？”。人们还可以解决诸如“这些技术足以解决这个问题吗？”或“序列必须具有多大的随机性才能表现出特定的典型行为？”之类的问题，人们必须发展一种详细的计算理论来解决这一问题。表明不存在某种类型的算法。同样，我们必须发展一种详细的可定义性理论，以表明不存在具有某些属性的简单例子，或者表明某些现象没有具体的分类。