FRG: Collaborative Research: Algorithmic Randomness

FRG：协作研究：算法随机性

• 批准号: 0652533
• 负责人: Theodore Slaman
• 金额: $ 2.74万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2010-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0652533&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Algorithmic; Randomness

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.

这个重点研究小组是许多网站研究人员的合作努力，这些网站将递归理论，复杂性理论和其他专业的想法带来有关算法随机性的问题。 重要的背景概念包括Kolmogorov的复杂性和Martin-Lof随机性的思想，这些想法已分别和共同受到了大量关注，并且在本提案中描述的许多例子和问题中都融合在一起。 项目期间要研究的问题包括Martin-Lof随机组与Hausdorff维度之间的关系或其他维度的措施，从半随机数据源中提取随机性的方法，弦线的复杂性类别的尺寸和其他功能，与kolmogorov较低的kolmogorov复杂性和雷诺的关系之间的独特性能和雷诺的关系的独特性能，以及雷诺的关系，该杂志的数学和雷神不足的次数可用于雷神不足。理论。这组研究人员研究的随机性形式是基于有关无限字符串的一些吸引人的想法，例如一系列无限重复的一系列硬币折腾的记录。 从直觉上讲，二进制字符串的kolmogorov复杂性，例如抛硬币的头部和尾巴的记录，是字符串最短的确定描述的长度。 语音和图像传输的数字化方法利用典型的语音信号或数字图像的规律性和重复，使用更少的空间或时间来记录声音或图像数据的时间比似乎必要的。 方面。 该小组的活动将包括研讨会，研究生的暑期学校以及合作旅行。