zbMATH — the first resource for mathematics

TT-functionals and Martin-Löf randomness for Bernoulli measures. (English) Zbl 1331.03030
Summary: For \(r\in[0,1]\), the Bernoulli measure \(\mu_r\) on the Cantor space \(\{0,1\}^{\mathbb{N}}\) assigns measure \(r\) to the set of sequences with 1 at a fixed position. In [R. D. Mauldin, “Problems in topology arising from analysis”, in: Open problems in topology. Amsterdam etc.: North-Holland. 617–629 (1990)] it is shown that for \(r,s\in[0,1]\), \(\mu_s\) is continuously reducible to \(\mu_r\) if any only if \(r\) and \(s\) satisfy certain purely number theoretic conditions (binomial reduciblility). We bring these results into the context of computability theory and Martin-Löf randomness and show that the continuous maps arising in [loc. cit.] are truth-table functionals (tt-functionals) on \(\{0,1\}^{\mathbb{N}}\). This allows us extend the characterization of continuous reductions between Bernoulli measures to include tt-functionals. It then follows from the conservation of randomness under tt-functionals that if \(s\) is binomially reducible to \(r\), then there is a tt-functional that maps every Martin-Löf random sequence for \(\mu_s\) to a Martin-Löf random sequences for \(\mu_r\). We are also able to show using results in [L. Bienvenu and C. Porter, Theor. Comput. Sci. 459, 55–68 (2012; Zbl 1283.68170)] that the converse of this statement is not true.
03D32 Algorithmic randomness and dimension
Zbl 1283.68170
Full Text: Euclid