Recursion Theory and Effective Aspects of Randomness

递归理论和随机性的有效方面

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

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.

Slaman建议研究随机性的有效方面。回答的主要问题是：“我们如何评估无限二进制序列的随机内容？”一种情况是充分理解的，其中无限序列x的0'sand 1是随机的，并且仅当独立选择每个数字时，并且对于0和1的值都具有相同的探索性。在这种情况下，x是有效的随机hosbeen等。以Martin-lof为特征，其特征是X具有几乎所有无限序列的属性，而Kolmogorov和其他人则以X的不可思议且难以形容的方式来看。 Slaman建议研究不均匀的情况，其有效随机性的相关标准及其对随机序列集的可能性。即使是最基本的问题也是开放的。例如，对于给定的Infi-Nite二进制序列X，在什么条件下，相对Towhich X的度量是随机的？这是一个经典的数学问题，鉴于单个数据集确定了将产生它的分布。定性地，x是随机的度量相关性集中在X的非随机方面上，从而将其与随机分离。量化X随机内容的其他方法包括X的初始段的复杂性以及X计算均匀随机序列的能力。该提议是调查所有这些和关系之间的关系。