Computability and Mathematical Definability

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

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.