Skip to main content
1 of 3

Non-relativized randomness (or Schnor?) notion w.r.t a measure

Riemann and Slaman have some great work classifying what reals are 1-random with respect to a measure $\mu$ relative to $\mu$. In that paper they cite Levin and Kautz (but not to refs I can find) for the claim that if $X$ is 1-random with respect to a computable measure $\mu$ then $X$ is of 1-random degree. They explain that the argument works by showing that $\mu$ is the image of $\lambda$ (Lebesgue measure) under a computable bijection $f$ and noting that $f^{-1}(X)$ will be 1-random if $X$ is 1-random with respect to $\mu$.

I have two questions related to this and since I've pretty much avoided randomness since grad school I figured they might have obvious answers to those working in the area.

  1. Does this claim generalize to computable (computable martingales) or Schnor (tests with uniformly computable measures) even in the presence of atoms? I'd be happy just with a reference to the proof so I can check without having to recreate it. If I was only considering continuous measures I'd probably have taken this for granted but without reading/reconstructing the proof it's not obvious to me this can be done in the presence of atoms.

  2. If we drop the restriction to computable measures but don't relativize the notion of randomness to a representation of $\mu$ (i.e. we demand our $\mu$ ML tests be made of actual c.e. sets not sets c.e. relative to $\mu$) is there a degree $\mathbf{d}$ such that every real $X$ is 1-random with respect to a $\mathbf{d}$ computable measure $\mu$? The result in Riemann and Slaman tells us that we can take $\mu$ to be computable in $X''$ but they are demanding that $X$ pass all $\mu$-c.e. ML tests. Can we make $\mathbf{d} \leq_T 0'$?

That's the main thrust of my question and if this is published somewhere I'd love to know. It might also be nifty to know what's the best we can do (any high degree? a low degree?). However, I have some vague memory that if you don't relativize you get a pathological notion so there might be a really trivial answer here.

P.S. I tagged this with martingales as that is how one defines computable randomness but I'm not sure if the tag should be used (even if technically accurate) to the notion as used in algorithmic randomness and couldn't figure out where to ask/discuss.