Recursion Theory and Effective Aspects of Randomness

斯拉曼建议研究随机性的有效方面。需要回答的中心问题是，“我们如何评估一个无限二进制序列的随机内容？”一种情况是很好理解的，其中0‘和1’的无限序列X是随机的当且仅当每个数字被独立地选择并且对于0和1的值具有相等的概率。在这种情况下，X的有效随机已经被Martin-Lof等价地刻画为X具有几乎所有无限序列的性质，并且被Kolmogorov等人等价地刻画为X的不可预测和不可描述。Slaman建议研究非均匀情况，有效随机性的相关标准，以及随机序列集的可能性。甚至最基本的问题也是悬而未决的。例如，对于给定的下标二进制序列X，在什么条件下存在相对于哪个X是随机的度量？这是一个经典的数学问题，假设一个单独的数据集确定一个将产生它的分布。在定性上，X是随机的相对度量集中在X的非随机方面，从而将这些方面与随机方面分开。其他量化X随机含量的方法包括X初始片段的复杂性以及X计算均匀随机序列的能力。我们的建议是调查所有这些问题以及它们之间的关系。

Slaman proposes to investigate the effective aspects of randomness. The central questionto be answered is, "How can we evaluate the random content of an infinite binarysequence?" One case is well understood, that in which an infinite sequence X of 0'sand 1's is random if and only if each digit is chosen independently and with equalprobability for the values of 0 and 1. In this case, X's being effectively random hasbeen equivalently characterized by Martin-Lof in terms of X's having the propertiesof almost all infinite sequences and by Kolmogorov and others in terms of X's beingunpredictable and indescribable. Slaman proposes to study the non-uniform case, itsassociated criteria for effective randomness, and its possibilities for the sets of randomsequences. Even the most basic questions are open. For example, for a given infi-nite binary sequence X, under what conditions does there exist a measure relative towhich X is random? This is a classic mathematical problem, given an individual dataset determine a distribution which would generate it. Qualitatively, a measure relativeto which X is random concentrates on the nonrandom aspects of X and thereby separatesthose from the random ones. Other ways to quantify X's random content includethe complexity of X's initial segments and X's ability to compute uniformly randomsequences. The proposal is to investigate all of these and the relationships betweenthem.