Randomness, Dimension and Computability

有效随机性的两个最基本的概念是柯尔莫戈洛夫复杂性和马丁-L随机性。第一种方法测量有限二进制串的信息量，而第二种方法反映的是随机的无限二进制序列没有“区分特征”的直觉。这两个概念都植根于可计算性理论，所以对随机性的研究自然会从可计算性理论以及测度论和信息论等经典数学学科中汲取方法和想法。另一方面，有效随机性的思想已经反馈到可计算性理论甚至逆向数学中，因此有效随机性与其他领域存在交叉滋养。此外，有效随机性理论本身已被证明是一个丰富的研究领域。Miller建议研究有效维度和计算能力之间的相互作用，随机性程度和计算能力之间的相互作用，平凡和低概念之间的相互作用，以及非单调投注策略的强度。如果生成序列的最短(二进制)计算机程序与序列本身的长度基本相同，则认为0和1序列是随机的。直观地说，随机序列没有可以用来给出压缩描述的模式。例如，由一百万个零组成的序列可以很容易地通过一个短程序生成，所以它不是随机的。另一方面，抛硬币一百万次(反面为零，正面为一)产生的序列很有可能是随机的。序列的最短程序长度称为序列的Kolmogorov复杂性；这个概念是在20世纪60年代引入的。如果一个无限序列的所有有限个初始段都足够随机，则它被认为是随机的。这相当于说，没有(半)可计算的投注策略可以通过试图预测序列的数字来赢得金钱。这项拟议的研究将解决有关随机性的基本问题。有些是投机性的，比如：“说一个序列比另一个序列更随机是什么意思？”这个问题已经导致了棘手的技术问题。它激发了米勒关于马丁-L随机数初始段复杂性的大部分工作，并在最近导致了一个似乎更接近于提供令人满意的答案的概念的形成。另一方面，技术工作往往揭示出更高层次的模式。例如，有越来越多的证据支持这一断言：“更多的随机序列作为先知没有那么有用，而在计算上无用的随机序列自动地更随机。”这又回到了“更随机”意味着什么的问题上。其他一些基本问题，比如“我们能在多大程度上从半随机的信息源中提取信息？”都带来了有趣的工作，但在技术层面上还没有穷尽。还有一些问题，比如“被允许以任何顺序押注序列数字的赌博策略有多强大？”尽管付出了集中的努力，但基本保持开放。这些都是已被证明具有有趣的技术方面的基本问题。

The two most fundamental notions in effective randomness are Kolmogorov complexity and Martin-Löf randomness. The first measures the information content of finite binary strings, while the second captures the intuition that a random infinite binary sequence has no "distinguishing features". Both notions are rooted in computability theory, so it is natural that the study of randomness draws methods and ideas from computability theory, as well as classical mathematical subjects like measure theory and information theory. On the other hand, ideas from effective randomness have fed back into computability theory and even reverse mathematics, so there is cross-fertilization between effective randomness and other fields. Moreover, the theory of effective randomness has proved to be a rich field of study in its own right. Miller proposes to study the interaction between effective dimension and computational power, the interaction between degrees of randomness and computational power, triviality and lowness notions, and the strength of non-monotonic betting strategies.A sequence of zeros and ones is considered random if the shortest(binary) computer program that generates the sequence has essentially the same length as the sequence itself. Intuitively, a random sequence has no patterns that can be exploited to give a compressed description. For example, the sequence consisting of a million zeros can be generated easily by a short program, so it is not random. On the other hand, there is a high probability that a sequence generated by flipping a coin a million times (tails is zero, heads is one) will be random. The length of the shortest program for a sequence is called the Kolmogorov complexity of the sequence; this notion was introduced in the 1960s. An infinite sequence is considered random if all of its finite initial segments are sufficiently random. This is equivalent to saying that no (semi-)computable betting strategy can win money trying to predict the digits of the sequence. The proposed research will address fundamental questions about randomness. Some are speculative, such as: "What does it mean to say that one sequence is more random that another?" This question has lead to difficult technical problems.It has motivated much of Miller's work on the initial segment complexity of Martin-Löf randoms and has recently led to the formulation of a notion that seems to come closer to providing a satisfactory answer. On the other hand, technical work often reveals higher level patterns. For example, there is a growing body of evidence supporting the assertion: "More random sequences are less useful as oracles and computationally useless random sequences are automatically more random." This ties back into the question about what it means to be "more random". Other basic questions, such as "To what extent can we distill information out of a semi-random source?"have lead to interesting work but have not been exhausted on a technical level. Still others, like "How powerful are betting strategies that are allowed to bet on the digits of a sequence in any order?" remain largely open, despite concentrated effort. These are all fundamental questions that have proved to have interesting technical aspects.