Initial Segment Complexities of Randomness Notions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Initial Segment Complexities of Randomness Notions

Résumé

Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of A's initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that Kolmogorov randomness coincides with Martin-Löf randomness relative to the halting problem K; that is, a set A is Martin-Löf random relative to K iff there is no function f such that for all m and all n > f(m) it holds that C(A(0)A(1)...A(n)) ≤ n − m. In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strongly random, Kurtz random relative to K, PA-incomplete Martin-Löf random and strongly Kurtz random; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A-recursive function f such that for all m and all n > f(m) it holds that C(A(0)A(1)...A(n)) ≤ n − m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies. In addition to this, characterisations of a similar style are also given for Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines.
Fichier principal
Vignette du fichier
03230259.pdf (182.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01054455 , version 1 (06-08-2014)

Licence

Paternité

Identifiants

Citer

Rupert Hölzl, Thorsten Kräling, Frank Stephan, Guohua Wu. Initial Segment Complexities of Randomness Notions. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. pp.259-270, ⟨10.1007/978-3-642-15240-5_19⟩. ⟨hal-01054455⟩
233 Consultations
108 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More