Initial Segment Complexities of Randomness Notions

摘要

Schnorr famously proved that Martin-Loef-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-Loef randomness relative to the halting problem K; that is, a set A is Martin-Loef 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.rnIn 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-Loef 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-Lof 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.rnIn 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.