Initial Segment Complexities of Randomness Notions

Abstract : 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.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 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. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.259-270, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_19〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054455
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:25:01
Dernière modification le : mercredi 9 août 2017 - 12:03:30
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 01:02:43

Fichier

03230259.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Rupert Hölzl, Thorsten Kräling, Frank Stephan, Guohua Wu. Initial Segment Complexities of Randomness Notions. Cristian S. Calude; Vladimiro Sassone. 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. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.259-270, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_19〉. 〈hal-01054455〉

Partager

Métriques

Consultations de la notice

236

Téléchargements de fichiers

57