Uniform relativization conjecture for computable randomness under layerwise maps

Assume that X\mathbb{X} and Y\mathbb{Y} are computable metric spaces, that {μa}aNN\{\mu_a\}_{a\in\mathbb{N}^{\mathbb{N}}} is a uniformly computable family of probability measures on X\mathbb{X}, and that {Ta}aNN\{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 a0NNa_0\in\mathbb{N}^{\mathbb{N}}, say that xXx\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 yYy\in\mathbb{Y} is (μa0)Ta0(\mu_{a_0})_{T_{a_0}}-computably random uniformly relativized to a0a_0, then there exists xXx\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.

Sources & referencesView supporting material

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.