Conditional Measure and the Violation of Van Lambalgen’s Theorem for Martin-Löf Randomness

详细信息    查看全文

• 作者：Bruno Bauwens
• 关键词：Martin ; Löf randomness ; Van Lambalgen’s theorem ; Conditional measure
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：314-323
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

Van Lambalgen’s theorem states that a pair (α, β) of bit sequences is Martin-Löf random if and only if α is Martin-Löf random and β is Martin-Löf random relative to α. 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 β for which the conditional probability P(⋅|β) 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]).