Recursion Theory and Effective Aspects of Randomness

Slaman建议调查随机性的有效方面。要回答的核心问题是，“我们如何评估一个无限二进制序列的随机内容？”有一种情况很好理解，即当且仅当0和1的无限序列X的每个数字都是独立选择的，并且0和1的值的概率相等时，X是随机的。在这种情况下，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.