期刊
THEORY OF COMPUTING SYSTEMS
卷 60, 期 2, 页码 314-323出版社
SPRINGER
DOI: 10.1007/s00224-016-9675-3
关键词
Martin-Lof randomness; Van Lambalgen's theorem; Conditional measure
资金
- project NAFIT [ANR-08-EMER-008-01]
Van Lambalgen's theorem states that a pair (alpha, beta) of bit sequences is Martin-Lof random if and only if alpha is Martin-Lof random and beta is Martin-Lof random relative to alpha. In [Information and Computation 209.2 (2011): 183-197, Theorem 3.3], Hayato Takahashi generalized van Lambalgen's theorem for computable measures P on a product of two Cantor spaces; he showed that the equivalence holds for each beta for which the conditional probability P(ai...|beta) is computable. He asked whether this computability condition is necessary. We give a positive answer by providing a computable measure for which van Lambalgen's theorem fails. We also present a simple construction of a computable measure for which conditional measure is not computable. Such measures were first constructed by Ackerman et al. ([1]).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据