{
  "id": "1608.08246",
  "version": "v1",
  "published": "2016-08-29T20:52:55.000Z",
  "updated": "2016-08-29T20:52:55.000Z",
  "title": "Relations between randomness deficiencies",
  "authors": [
    "Gleb Novikov"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "The notion of random sequence was introduced by Martin-Loef in 1966. At the same time he defined the so-called randomness deficiency function that shows how close are random sequences to non-random (in some natural sense). Other deficiency functions can be obtained from the Levin-Schnorr theorem, that describes randomness in terms of Kolmogorov complexity. The difference between all of these deficiencies is bounded by a logarithmic term. In this paper we show that the difference between some deficiencies can be as large as possible.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-08-29T20:52:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random sequence",
      "randomness deficiency function",
      "natural sense",
      "levin-schnorr theorem",
      "kolmogorov complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}