Computability and Mathematical Definability

Slaman建议研究有效的，更普遍的定义，数学现象的方面，如通用性，紧凑性和随机性。 本文研究的一个中心问题是给出无限二元序列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.