{
  "id": "1111.1064",
  "version": "v1",
  "published": "2011-11-04T08:11:49.000Z",
  "updated": "2011-11-04T08:11:49.000Z",
  "title": "The typical Turing degree",
  "authors": [
    "George Barmpalias",
    "Adam R. Day",
    "Andrew E. M. Lewis"
  ],
  "comment": "42 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "The Turing degree of a real measures the computational difficulty of producing its binary expansion. Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1 law that for any property which may or may not be satisfied by any given Turing degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the \\emph{typical} degree satisfies the property, or else the typical degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. A similar analysis can be made in terms of Baire category, where a standard form of genericity now plays the role that randomness plays in the context of measure. We describe and prove a number of results in a programme of research which aims to establish the properties of the typical Turing degree, where typicality is gauged either in terms of Lebesgue measure or Baire category.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-11-04T08:11:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D28"
    ],
    "keywords": [
      "typical turing degree",
      "lebesgue measure",
      "degree satisfies",
      "baire category",
      "computational difficulty"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 42,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.1064B"
    }
  }
}