pith. sign in

arxiv: 1110.1860 · v2 · pith:3WC6HI4Hnew · submitted 2011-10-09 · 🧮 math.LO

Effective randomness, strong reductions and Demuth's theorem

classification 🧮 math.LO
keywords theoremcomputabledemuthrandomrandomnessturingmartin-lreal
0
0 comments X
read the original abstract

We study generalizations of Demuth's Theorem, which states that the image of a Martin-L\"of random real under a tt-reduction is either computable or Turing equivalent to a Martin-L\"of random real. We show that Demuth's Theorem holds for Schnorr randomness and computable randomness (answering a question of Franklin), but that it cannot be strengthened by replacing the Turing equivalence in the statement of the theorem with wtt-equivalence. We also provide some additional results about the Turing and tt-degrees of reals that are random with respect to some computable measure.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.