2015/09/09 by Bauwens, Bruno
#03D32 #68Q30 #F.4.1 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1509.02884
Van Lambalgen's theorem states that a pair (α,β) of bitsequences 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 measure for which conditional measure is not computable. Such measures were first constructed by N. Ackerman, C. Freer and D. Roy in [Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 107-116. IEEE (2011)].