Recursion Theory and Effective Aspects of Randomness

斯拉曼建议研究随机性的有效方面。要回答的中心问题是，“我们如何才能评估一个无限binarysequence的随机内容？有一种情况是很容易理解的，即一个由0和1组成的无限序列X是随机的，当且仅当每个数字都是独立选择的，并且0和1的值的概率相等。在这种情况下，X的有效随机性已经被马丁-洛夫等价地表征为X具有几乎所有无限序列的性质，并且被柯尔莫哥洛夫和其他人等价地表征为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.