1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. It's theorem 6.12.9 in Downey & Hirschfeldt. The answer should be yes, with the caveat that it won't hold if $X$ is an atom of $\mu$.
  2. Levin proved the existence of a $\mu$ such that every real passes all $\mu$-c.e. ML tests, which is stronger than what you're requiring. For what you're asking, I believe we can use c.e. permitting to construct such a $\mu$ below every non-computable c.e. degree. The goal is to ensure that there are no c.e. $\mu$-ML tests. Choose some $2^{-d}$ of measure to attack the $e$th test. Assign it somewhere with some large use, and wait for the $(d+1)$-level of the $e$th test to enumerate some neighborhood. When it does, wait for permission to shift that $2^{-d}$ of measure to this neighborhood (thus proving that this is not an ML-test). Meanwhile, begin again with a larger $d$ in the usual c.e. permitting fashion. In fact, I believe this could be made to work with hyperimmune permitting.
$\endgroup$
2
  • $\begingroup$ Thanks so much! I appreciate it. As I said it's been awhile since I touched randomness. $\endgroup$ Feb 18, 2020 at 18:23
  • $\begingroup$ Ohh and I see your answer to 2 explains my vague memory that something goes very very wrong. $\endgroup$ Feb 18, 2020 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.