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 Krecursive 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. © IFIP International Federation for Information Processing 2010.