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.

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