Uniform relativization conjecture for computable randomness under layerwise maps

About 11 years old · traced to

Assume that X\mathbb{X} and Y\mathbb{Y} are computable metric spaces, that {μa}a∈NN\{\mu_a\}_{a\in\mathbb{N}^{\mathbb{N}}} is a uniformly computable family of probability measures on X\mathbb{X}, and that {Ta}a∈NN\{T_a\}_{a\in\mathbb{N}^{\mathbb{N}}} is a family of layerwise maps Ta ⁣:(X,μa)→YT_a\colon(\mathbb{X},\mu_a)\rightarrow\mathbb{Y}, with TaT_a Schnorr layerwise computable uniformly in aa. For a0∈NNa_0\in\mathbb{N}^{\mathbb{N}}, say that x∈Xx\in\mathbb{X} is μa0\mu_{a_0}-computably random uniformly relativized to a0a_0 when it passes every uniformly relativized computable randomness test as defined in the setup. Uniform relativization conjecture. If y∈Yy\in\mathbb{Y} is (μa0)Ta0(\mu_{a_0})_{T_{a_0}}-computably random uniformly relativized to a0a_0, then there exists x∈Xx\in\mathbb{X} which is μa0\mu_{a_0}-computably random uniformly relativized to a0a_0 such that y=Ta0(x)y=T_{a_0}(x). This is presented as the full generalization of the non-relativized result to uniform relativization; the surrounding discussion explains why uniform relativization is the relevant strengthening for computable randomness. The supplied text gives no resolution, so the conjecture remains open.

References

Primary source

Jason Rute, “When does randomness come from randomness?”, arXiv:1508.05082 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.