{
  "id": "1110.1860",
  "version": "v2",
  "published": "2011-10-09T17:11:42.000Z",
  "updated": "2011-10-26T07:19:48.000Z",
  "title": "Effective randomness, strong reductions and Demuth's theorem",
  "authors": [
    "Laurent Bienvenu",
    "Christopher Porter"
  ],
  "comment": "Submitted to Theoretical Computer Science",
  "categories": [
    "math.LO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-10-26T07:19:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "strong reductions",
      "effective randomness",
      "random real",
      "demuths theorem holds",
      "study generalizations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.1860B"
    }
  }
}