Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Wednesday, August 6, 2014 - 4:25:01 PM
Last modification on : Wednesday, August 9, 2017 - 12:03:30 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 1:02:43 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads