Randomness and Computability

有效随机性的两个最基本的概念是Kolmogorov复杂性和Martin-Lof随机性。第一种方法测量有限二进制串的信息量，而第二种方法反映的是随机的无限二进制序列没有“区分特征”的直觉。这两个概念都植根于可计算性理论，因此，研究随机性的方法和思想来自可计算性理论，以及测度论和信息论等核心数学学科，这并不令人惊讶。然而，有效随机性理论本身已被证明是一个丰富的研究领域。Miller建议研究非单调投注策略的强度、具有正有效Hausdorff维度的序列的可计算能力、随机度和K平凡度。如果生成序列的最短(二进制)计算机程序与序列本身具有基本相同的长度，则认为0和1序列是随机的。直观地说，随机序列没有可以用来给出压缩描述的模式。例如，由一百万个零组成的序列可以很容易地通过一个短程序生成，所以它不是随机的。另一方面，抛硬币一百万次(反面为零，正面为一)产生的序列很有可能是随机的。序列的最短程序长度称为序列的Kolmogorov复杂性；这个概念是在20世纪60年代引入的。如果一个无限序列的所有有限个初始段都足够随机，则它被认为是随机的。这相当于说，没有(半)可计算的投注策略可以通过试图预测序列的数字来赢得金钱。拟议的研究将解决有关随机性的基本问题，包括：(1)允许以任何顺序押注序列数字的可计算投注策略有多强大；(2)是否有可能从半随机来源中提取信息来产生随机序列，或者至少产生信息密度更高的序列；(3)说一个无限序列比另一个无限序列更随机是什么意思；(4)无限序列在计算上有多弱？

The two most fundamental notions in effective randomness are Kolmogorov complexity and Martin-Lof 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 not surprising that the study of randomness draws methods and ideas from computability theory, as well as core mathematical subjects like measure theory and information theory.However, the theory of effective randomness has proved to be a rich field of study in its own right. Miller proposes to study the strength of non-monotonic betting strategies, the computable power of sequences with positive effective Hausdorff dimension, degrees of randomness, and K-triviality.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, including: (1) How powerful are computable betting strategies that are allowed to bet on the digits of a sequence in any order; (2) Is it possible to distill information out of a semi-random source to produce a random sequence or, at least, a sequence that has higher information density; (3) What does it mean to say that one infinite sequence is more random that another (4) How computationally weak are the infinite?