Journal
THEORY OF COMPUTING SYSTEMS
Volume 60, Issue 2, Pages 314-323Publisher
SPRINGER
DOI: 10.1007/s00224-016-9675-3
Keywords
Martin-Lof randomness; Van Lambalgen's theorem; Conditional measure
Categories
Funding
- project NAFIT [ANR-08-EMER-008-01]
Ask authors/readers for more resources
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]).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available