pith. sign in

arxiv: 1509.02884 · v5 · pith:R2C6ZT2Snew · submitted 2015-09-09 · 🧮 math.LO

Van Lambalgen's theorem fails for some computable measure

classification 🧮 math.LO
keywords computabletheorembetalambalgenmeasurealphamartin-lrandom
0
0 comments X
read the original abstract

Van Lambalgen's theorem states that a pair $(\alpha,\beta)$ of bitsequences is Martin-L\"of random if and only if $\alpha$ is Martin-L\"of random and $\beta$ is Martin-L\"of 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(\cdot | \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 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)].

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.