FRG: Collaborative Research: Algorithmic Randomness

这个聚焦研究小组是由许多站点的研究人员共同努力的，他们将递归理论、复杂性理论和其他专业的想法带到关于算法随机性的问题上。重要的背景概念包括科尔莫戈洛夫复杂性和马丁-洛夫随机性的概念，这两个概念分别和共同受到了大量关注，并在本提案中描述的许多例子和问题中结合在一起。项目中要研究的问题包括随机集的Martin-Lof与Hausdorff维度或其他维度测量之间的关系，从半随机数据源中提取随机性的方法，字符串复杂性类别的维度和其他性质，具有低Kolmogorov复杂性的集合的独特性质，以及算法随机性和逆数学之间的关系，后者试图理解特定理论所需的公理强度。这组研究人员研究的随机性形式基于一些关于无限字符串的吸引人的想法，例如无限次重复抛硬币序列的记录。直观地说，一个二进制字符串的柯尔莫戈罗夫复杂性就是对该字符串最短的明确描述的长度，就像掷硬币的头和尾的记录一样。语音和图像传输的数字化方法利用典型语音信号或数字化图像中的规律性和重复性，使用比看起来必要的更少的空间或时间来记录声音或图像数据。从柯尔莫戈洛夫复杂性的观点来看，真正的随机二进制串可能是它自己最短的描述，或者几乎是这样。这个研究小组研究的一些问题寻求建立具有相同复杂性的字符串子集的性质，例如它们的维度。该小组的活动将包括研讨会、研究生暑期学校和协作旅行。

This Focused Research Group is a collaborative effort by researchers at many sites who bring ideas from recursion theory, complexity theory, and other specialties to bear on questions about algorithmic randomness. Important background notions include the ideas of Kolmogorov complexity and Martin-Lof randomness, which have separately and jointly received large amounts of attention, and which come together in many of the examples and problems described in this proposal. Issues to be studied during the project include relationships between Martin-Lof random sets and Hausdorff dimension or other measures of dimension, methods for extracting randomness from a semi-random source of data, dimensions and other properties of complexity classes of strings, distinctive properties of sets with low Kolmogorov complexity, and relationships between algorithmic randomness and reverse mathematics, which seeks to understand the axiomatic strength required by particular theories.The forms of randomness studied by this group of researchers are based on some appealing ideas regarding infinite strings, such as the record of an infinitely repeated series of coin tosses. Intuitively, the Kolmogorov complexity of a binary string like the record of heads and tails from coin tosses is the length of the shortest definitive description of the string. Digitization methods for voice and picture transmission take advantage of the regularity and repetition in typical voice signals or digitized images, using much less space or time to record the sound or image data than might seem necessary.From the point of view of Kolmogorov complexity, a genuinely random binary string is probably its own shortest description, or nearly so.Some of the problems studied by this research group seek to establish properties of subsets of strings that have the same complexity, such as their dimension. Activities of the group will include workshops, summer schools for graduate students, and travel for collaboration.