Cover Image
QR Code

LIMIT COMPLEXITIES, MINIMAL DESCRIPTIONS, AND n -RANDOMNESS.

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n , $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as t...

Full description

Published in:Journal of Symbolic Logic Vol. 90; no. 3; pp. 1261 - 1277
Main Authors: DOWNEY, RODNEY, LIU, LU, NG, KENG MENG, TURETSKY, DANIEL
Format: Article
Published: Cambridge University Press Sep2025
Subjects:
Kolmogorov complexity
Algorithmic randomness
Mathematical formulas
Complexity (Philosophy)
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=190715101&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 190715101
    longDbName: Humanities International Complete
    uiTag: AN
  controlInfo:
    bkinfo:
    jinfo:
      jid:
        00224812
        3TY
      jtl: Journal of Symbolic Logic
      issn: 00224812
      maglogo: N
    pubinfo:
      dt: Sep2025
      vid: 90
      iid: 3
      pid: 15979
      pub: Cambridge University Press
    artinfo:
      ui:
        190715101
        10.1017/jsl.2024.41
      ppf: 1261
      ppct: 16
      formats:
      tig:
        atl: LIMIT COMPLEXITIES, MINIMAL DESCRIPTIONS, AND n -RANDOMNESS.
      aug:
        au:
          DOWNEY, RODNEY
          LIU, LU
          NG, KENG MENG
          TURETSKY, DANIEL
        affil:
          SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY PO BOX 600, WELLINGTON 6140, NEW ZEALAND E-mail
          SCHOOL OF MATHEMATICS AND STATISTICS HNP-LAMA, CENTRAL SOUTH UNIVERSITY CHANGSHA, HUNAN 410083, CHINA E-mail
          DIVISION OF MATHEMATICAL SCIENCES SCHOOL OF PHYSICAL AND MATHEMATICAL SCIENCES NANYANG TECHNOLOGICAL UNIVERSITY 21 NANYANG LINK, SINGAPORE 637371, SINGAPORE E-mail
      su:
        Kolmogorov complexity
        Algorithmic randomness
        Mathematical formulas
        Complexity (Philosophy)
      sug:
        subj:
          Kolmogorov complexity
          Algorithmic randomness
          Mathematical formulas
          Complexity (Philosophy)
      keyword:
        limit complexity
        minimal description
      ab: Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n , $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n -randomness is definable purely in terms of K. To do this we extend a certain "limsup" formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions.
      pubtype: Academic Journal
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2025
    holdings:
      @attributes:
        islocal: N