• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Separations of non-monotonic randomness notions
【24h】

Separations of non-monotonic randomness notions

机译：非单调随机性概念的分离

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received the most attention are perhaps Martin-Loef (ML) randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of ML randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e. strategies that do not bet on bits in order. The subsequent 'non-monotonic' notion of randomness, now called Kolmogorov-Loveland randomness, has been shown to be quite close to ML randomness, but whether these two classes coincide remains a fundamental open question. In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e. strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from ML randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.
机译：在算法随机性理论中，通过博弈论方法定义了多个随机序列概念，而受到最多关注的概念可能是马丁·洛夫（ML）随机性和可计算随机性。后者的概念是Schnorr引入的，它很自然：如果没有完整的可计算策略通过按顺序押注位在其上获得成功，则无限二进制序列是可计算的随机数。然而，可计算随机序列可以具有人们可能认为与随机不兼容的特性，特别是，存在可高度压缩的可计算随机序列。在这方面和其他方面，ML随机性的概念表现得更好，另一方面，就mar而言，它的定义自然而然地少了。 Muchnik在阐述Kolmogorov和Loveland的思想时，还通过允许非单调策略（即不按顺序下注的策略）完善了Schnorr的模型。随后的“非单调”随机性概念（现称为Kolmogorov-Loveland随机性）已非常接近ML随机性，但是这两个类别是否重合仍然是一个基本的开放性问题。为了更好地理解非单调随机性的概念，Miller和Nies引入了一些有趣的中间概念，其中仅允许非自适应策略，即仍然可以非单调下注的策略，但下注位置的顺序是事先已知的（并且是可计算的）。最近，Kastermans和Lempp证明了这些概念不同于ML随机性。我们继续研究Miller和Nies引入的非单调随机性概念，并获得有关此类序列可能发生和可能不会发生的初始片段的Kolmogorov复杂性的结果，这些结果随后暗示了这些随机性概念按顺序进行了完整分类力量。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号