# Initial Segment Complexities of Randomness Notions

Rupert Hölzl, Thorsten Kräling, Frank Stephan, Guohua Wu

► To cite this version:

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

HAL Id: hal-01054455

https://inria.hal.science/hal-01054455

Submitted on 6 Aug 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Initial Segment Complexities of Randomness
Notions

Rupert Hölzl<fnref n="1" />*, Thorsten Kräling<fnref n="1" />, Frank Stephan<fnref n="2" />** and Guohua Wu<fnref n="3" />

**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)) \le 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.

# 1 Introduction

Kolmogorov complexity [9, 13] aims to describe when a set is random in an
algorithmic way. Here randomness means that no type of patterns can be exploited
by an algorithm in order to generate initial segments of the characteristic function

<footnote n="1">¹ Institut für Informatik, Universität Heidelberg, INF 294, 69120 Heidelberg, Germany,
hoelzl@math.uni-heidelberg.de and kraeling@informatik.uni-heidelberg.de</footnote>

<footnote n="2">² Department of Mathematics, National University of Singapore, 2 Science Drive 2,
Singapore 117543, Singapore, fstephan@comp.nus.edu.sg</footnote>

<footnote n="3">³ Division of Mathematical Sciences, School of Physical and Mathematical Sciences,
College of Science, Nanyang Technological University, Singapore, guohua@ntu.edu.sg</footnote>

<footnote>* R. Hölzl is supported by DFG grant ME 1806/3-1.</footnote>

<footnote>** F. Stephan is supported in part by the NUS grants R146-000-114-112 and R252-000-308-112.</footnote>
from shorter programs. Randomness notions have been formalised by Martin-Löf [10], Schnorr [18] and others. A special emphasis was put on describing randomness of a set A in terms of the complexity of the initial segments $A(0)A(1)\dots A(n)$. The first important result in that direction was that Schnorr [19] proved that a set A is Martin-Löf random if and only if for almost all n the prefix free Kolmogorov complexity $H(A(0)A(1)\dots A(n))$ of the (n+1)-th initial segment is at least n. It is easy to see that the counterpart of this characterisation is that a set A is not Martin-Löf random iff there is an A-recursive function f such that $H(A(0)A(1)\dots A(f(m))) \le f(m) - m$ for all m. In other words, one can find — relative to A — points to witness the non-randomness effectively. It should be noted that the function f has to be taken relative to A and not relative to some fixed oracle B independent of A as the sets 2-generic relative to B are not Martin-Löf random but would not admit a B-recursive function f witnessing the non-randomness in the way just mentioned.

The scope of the present paper is to study the notions of randomness beyond Martin-Löf randomness. These are the relativised versions “Kurtz random relative to K”, “Schnorr random relative to K” and “Kolmogorov random” which coincides with “Martin-Löf random relative to K” where K is the halting problem or any other creative set. In addition, the two independently defined notions of “Demuth random” and “strongly random” are considered. Strong randomness is by some authors considered to be the next counterpart of Kurtz randomness, although it is not the relativised version; therefore they call Kurtz random also “weakly random” and strongly random also “weakly 2-random” [13]. Strong randomness [8, 17] has various nice characterisations, in particular the following: A is strongly random iff A is Martin-Löf random and forms a minimal pair with K with respect to Turing reducibility [4, Footnote 2]. For these notions, in order to quantify the degree of non-randomness of a sequence, one studies from which value $f(m)$ onwards all initial segments can be compressed by $m$ bits. That is, one looks at functions $f$ such that $C(A(0)A(1)\dots A(n)) \le n - m$ for all $n > f(m)$; here $f$ might also be an upper bound of the least possible point with this property as one might want to have that $f$ is in a certain Turing degree. This idea is quite natural as Kolmogorov random is just the notion of randomness which is defined by the absence of any such $f$ and which coincides with Martin-Löf random relative to K.

The main results of this article will be that other randomness notions can be characterised in similar ways. The characterisations of these notions will differ in how the function $f$ can be computed (e.g., relative to which oracles) and whether the compressibility condition holds for infinitely many or for all $m$. Note that due to finite modifications of $f$ it would be equivalent to postulate the condition for all $m$ or for almost all $m$. Several proofs make use of this fact.

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 [1] gave one in terms of Kolmogorov complexity defined by computable machines. There is a close connection between the plain Kolmogorov complexity $C$ and prefix-free Kolmogorov complexity $H$. This is
formalised in the following remark and this connection helps to establish many bounds obtained for C also for H.

**Remark 1.** If $C(x) \le |x| - 1 - 3m$ with a minimal plain code $x^*$ for $x$, and if $n^*$ and $m^*$ are minimal prefix-free codes for $n := |x|$ and $m$, respectively, then some prefix-free machine can use $n^*m^*0^k1x^*$ as a prefix-free code for $x$, where $k$ is chosen such that $|0^k1x^*| = n - 3m$.

It easily follows that there is a constant $c$ such that whenever a set $A$ and a function $f$ satisfy that $C(A(0)A(1)\dots A(n)) \le n - 3m$ for all $m$ and all $n > f(m)$, then $A$ and $f$ also satisfy that for all $m > c$ and all $n > f(m)$ it holds that $H(A(0)A(1)\dots A(n)) \le n + H(n) - m$.

We will also use the following theorem.

**Theorem 2 (Chaitin's Counting Theorem [3]).** There is a constant $c$ such that for all $n$ and $m$ it holds that

$$|\{\sigma : |\sigma| = n + 1 \wedge H(\sigma) \le n + H(n) - m\}| \le 2^{n - m + c}.$$

For the scientific background of this paper, the reader is referred to the usual textbooks on recursion theory [15, 16, 20] and algorithmic randomness [2, 9, 13].

## 2 Characterising Strong Randomness

Nies [13, Problem 3.6.23] asks whether one can characterise strong randomness via the growth of the initial segment complexity. In the present paper, an answer will be provided, but for that answer the growth-rate depends also on the Turing degree of the set $A$ for which it is asked whether it is strongly random. After the characterisation in Theorem 5, it will be shown in two further results that there is no obvious way to simplify the characterisation.

**Remark 3.** An open r.e. class $V_e$ consists of sets $A$ such that for each member $A \in V_e$ it is verified in some finite time $s$ that $A$ belongs to $V_e$; let $V_{e,s}$ be the class of all $A$ such that it is verified in time $s$ that $A$ belongs to $V_e$. Now the notion is chosen such that whenever $A \in V_{e,s}$ and $B(m) = A(m)$ for all $m \le s$ then $B \in V_{e,s}$ as well. An open r.e. class $V_e$ is called finitely generated iff there is a step-number $s$ such that $V_{e,s} = V_e$.

Furthermore, in the following, let $C$ be the plain and $H$ be the prefix-free Kolmogorov complexity. $K$ denotes the halting problem. $f_s$ is then the $s$-th approximation of a $K$-recursive function $f$, the mapping $x, s \mapsto f_s(x)$ is recursive in both inputs. The following notion was originally introduced by Kurtz [8] and is one of the central notions of this paper.

**Definition 4 (Kurtz [8]).** A set $A$ is called strongly random iff there is no uniform sequence $V_0, V_1, V_2, \dots$ of open r.e. classes such that $\mu(V_e) \to 0$ for $e \to \infty$ and $A \in \bigcap_e V_e$.
The next result gives a characterisation of strong randomness in the desired form.

**Theorem 5.** The following are equivalent for a set A.

(a) A is not strongly random.

(b) There is an A-recursive function f and a K-recursive function g such that for all m and all n ≥ f(g(m)) it holds that C(A(0)A(1)...A(n)) ≤ n - m.

(c) There is an A-recursive function f and a K-recursive function g such that for all m and all n ≥ f(g(m)) it holds that H(A(0)A(1)...A(n)) ≤ n + H(n) - m.

*Proof.* (a) ⇒ (b): Let $V_0, V_1, V_2, ...$ be the test which witnesses that A is not strongly random. Now let $h(m)$ be the first index $e$ with $\mu(V_e) \le 2^{-2m-1}$ and let $h_0, h_1, h_2, ...$ be a recursive approximation to $h$; this approximation is from below, as one can define that $h_0(m) = 0$ and

$$h_{s+1}(m) = \begin{cases} h_s(m) & \text{if } \mu(V_{h_s(m),s}) \le 2^{-2m-1}; \\ h_s(m) + 1 & \text{otherwise.} \end{cases}$$

Now let $g(m) = \langle m, s \rangle$ for the first $s$ such that $h_s(m) = h(m)$. Next define the A-recursive function $f$ which assigns to $\langle m, s \rangle$ the first encountered $\ell > s + m$ satisfying

$$A(0)A(1)...A(\ell) \cdot \{0,1\}^{\infty} \subseteq V_{h_s(m)}.$$

Now one defines a plain machine $M$ such that, for all $m, n$ with $n \ge 2m+1$ and all $x \in \{0,1\}^{n-1-2m}$, $M(1^m 0x)$ is the $x$-th string $y$ of length $n$ for which it is verified in time $n$ that $y \cdot \{0,1\}^{\infty} \subseteq V_{h_n(m)}$; for small $n$ there might be too many of these strings $y$ and then only the first $2^{n-1-2m}$ of them are in the range of $M$; but for $n \ge f(g(m))$ it holds that $h_n(m) = h(m)$ and that therefore by the choice of $V_{h_n(m)}$ there are at most $2^{n-1-2m}$ of these strings and each of them occurs in the range of $M$. One of these strings is the prefix of length $n$ of A. Hence, there is a constant $c$ such that for the function $m \mapsto f(g(m+c))$ and every $n$ greater than the value of this function it holds that

$$C(A(0)A(1)...A(n)) \le n - m.$$

(b) ⇒ (c): This follows from Remark 1 and a substitution of $g$ by $\tilde{g}(m) := g(3m)$.

(c) ⇒ (a): It follows from Chaitin's Counting Theorem 2 that if $\ell$ is sufficiently large, then for all $n$ there are at most $2^{n-m+\ell}$ strings $\sigma$ of length $n+1$ with $H(\sigma) \le n+H(n)-m$. Let $g \le_T K$ and $f = \varphi_e^A$ be the functions from condition (c). Without loss of generality fix them such that $g$ is recursively approximable from below by $g_0, g_1, g_2, ...$ and that $f$ is monotone. Now define $V_{\langle m,n,s \rangle}$ as the class of all sets $B$ satisfying one of the following conditions:

1. $\exists t > s[g_t(m) \ne g_s(m)$ or $H_t(n) \ne H_s(n)];$

2. $\varphi_e^B(g_s(m)) \downarrow > n$;

3. $H(B(0)B(1)...B(n)) \le n + H_s(n) - m.$
Note that the first condition ensures that *all* sets are enumerated into those classes $V_{\langle m,n,s \rangle}$ where the parameters are not chosen adequately.

The set $A$ is in every class $V_{\langle m,n,s \rangle}$ as whenever the first condition and the second condition do not put $A$ into $V_{\langle m,n,s \rangle}$ then $g_s(m) = g(m)$ and $H_s(n) = H(n)$ and $\varphi_e^A(g(m)) \le n$ and therefore $H(A(0)A(1)\dots A(n)) \le n + H(n) - m$. Furthermore, one can for every $m$ choose the $n$ so large compared to $m$ and the $s$ so large compared to $m,n$ that $g_t(m) = g(m)$ and $H_t(m) = H(n)$ for all $t \ge s$ and $\varphi_e^B(g(m)) \ge n$ only for a class of $B$ of measure below $2^{-m}$. It follows then that $\mu(V_{\langle m,n,s \rangle})$ is at most $2^{-m} + 2^{\ell-m}$ as the first condition of putting oracles $B$ into $V_{\langle m,n,s \rangle}$ does not apply, the second condition contributes a class of oracles with measure $2^{-m}$ and the third condition contributes a class of oracles with measure $2^{\ell-m}$. As $\ell$ is a constant, one can come as close to measure 0 as desired by starting off with a sufficiently large $m$ and then choosing $n$ in dependence of $m$ and $s$ in dependence on $m,n$ as indicated.

From this sequence of the $V_{\langle m,n,s \rangle}$, one can construct a new sequence of the form $e \mapsto \cap_{n \le e, m \le s} \cap_{e \le e} V_{\langle m,n,s \rangle}$ which satisfies that the measures of the members tend to 0 and that each member contains the set $A$ as an element. Hence this sequence witnesses that $A$ is not strongly random. $\square$

Note that in the above construction the machine $M$ can be chosen such that its domain is recursive, that is, $M$ can be chosen as a decidable machine.

The above conditions (b) and (c) contain a function which is a concatenation of an $A$-recursive and a $K$-recursive function. One might ask whether this condition could be simplified by taking only a $K$-recursive or only an $(A \oplus K)$-recursive function. The answer is “no” as these two choices will give rise to other randomness notions as shown in the next two results.

**Theorem 6.** The following are equivalent for every set $A$:

(a) $A$ is not Martin-Löf random relative to $K$;

(b) There is $f \le_T A \oplus K$ such that $\forall m \forall n > f(m) [C(A(0)A(1)\dots A(n)) \le n - m]$;

(c) There is $f \le_T A \oplus K$ such that $\forall m \forall n > f(m) [H(A(0)A(1)\dots A(n)) \le n + H(n) - m]$.

*Proof.* If $A$ is Martin-Löf random relative to $K$ then the two conditions (b) and (c) cannot be satisfied for any function $f$ by known results [11, 12, 14]. So assume that (a) holds.

Let $U^K$ be a prefix-free universal machine relative to the oracle $K$ and $x, s \mapsto U_s(x)$ be a recursive approximation to this machine such that every $U_s$ is prefix-free. Now there is an $A \oplus K$-recursive function which produces for every $m$ a number $f(m)$ such that there exists $z$ with $|z| + 2m < |U^K(z)| \le f(m)$, $U^K(z)$ is a prefix of $A$ and $U_s(z) \downarrow = U^K(z)$ for all $s \ge \tilde{f}(m)$.

Now one can construct a plain machine $\tilde{U}$ which sends every input of the form $xy$ with $x \in \text{dom}(U_{|xy|})$ to $U_{|xy|}(x) \cdot y$ and which is undefined on inputs which cannot be brought into this form; note that because of prefix-freeness for each input $u$ the splitting into $xy$ is unique or does not exist. Now for all $m$ there is a $z$ as above. If $U^K(z) = A(0)A(1)\dots A(k)$, then it follows that $\tilde{U}(zA(k+1)A(k+2)\dots A(n)) = U_{n+1}(z) \cdot A(k+1)\dots A(n) = A(0)A(1)\dots A(n)$
and hence $C(A(0)A(1)\dots A(n)) \le (k-2m)+(n-k)+O(1) \le n-m$ for almost all $m$ and all $n > f(m)$. Note that we can modify $f$ for finitely many $m$ such that $f$ satisfies the condition (b). Remark 1 establishes that (c) follows from (b). $\square$

The next result characterises Kurtz randomness relative to $K$.

**Definition 7.** A set $A$ is called *Kurtz-random* iff it is contained in every r.e. class of Lebesgue measure 1.

**Theorem 8.** The following are equivalent for every set $A$:

(a) $A$ is not Kurtz random relative to $K$;

(b) There is a sequence of finitely generated r.e. open classes such that each class contains $A$ and the infimum of their measures is 0;

(c) There is a $K$-recursive function $f$ such that for all $m$ and all $n > f(m)$ it holds that $C(A(0)A(1)\dots A(n)) \le n-m$;

(d) There is a $K$-recursive function $f$ such that for all $m$ and all $n > f(m)$ it holds that $H(A(0)A(1)\dots A(n)) \le n + H(n) - m$.

**Proof.** (a) $\Rightarrow$ (b): By definition, $A$ is covered by a $K$-recursive Kurtz-test. According to Bienvenu and Merkle [1, Definition 7] a ($K$-recursive) Kurtz-test is given by a recursive ($K$-recursive) function $f$ which determines for each $m$ a finite set $D_{f(m)}$ of strings such that for all $m$, $A$ has a prefix in $D_{f(m)}$ and the measure of the class of all sets $B$ with a prefix in $D_{f(m)}$ is at most $2^{-m}$. For the given $K$-recursive Kurtz test, let $f_0, f_1, f_2, \dots$ be a recursive approximation of the corresponding function $f$. Now let $V_{\langle m,s \rangle} = \{B: B$ has a prefix in $D_{f_t(m)}$ for some $t \ge s\}$. It is clear that every $V_{\langle m,s \rangle}$ contains $A$ as a prefix of $A$ is in almost all $D_{f_t(m)}$. Furthermore, as the $f_t$ converge, the union of all $D_{f_t(m)}$ with $t \ge s$ is finite and contains only finitely many strings; that is, the r.e. class generated by it is finitely generated. Furthermore, for every $m$ and every sufficiently large $s$, $f_t(m) = f(m)$ for all $t \ge s$ and hence $V_{m,s}$ has at most measure $2^{-m}$.

(b) $\Rightarrow$ (c): Let $V_0, V_1, V_2, \dots$ be a given sequence of finitely generated r.e. open classes as in condition (b). Let $V_{e,s}$ be the class of all $B$ for which is verified in time $s$ that they belong to $V_e$; by choice there is for every $e$ an $s$ with $V_{e,s} = V_e$. For every $m$ let $g_s(m)$ be the smallest number $e$ such that $\mu(V_{e,s}) < 2^{-3m-1}$.

This function $g_s(m)$ is always defined as it is bounded by the index $g(m)$ of the first class whose measure is strictly below $2^{-3m-1}$. Now let $f(m)$ be the first step $s$ such that $g_s(m) = g(m)$ and $V_{g_s(m),s} = V_{g(m)}$, that is, all sets which are put into $V_{g(m)}$ are already enumerated into it. Observe that $g_t(m) = g(m)$ for all $t \ge f(m)$. Now let $M(1^m 0x)$ be the $x$-th string $y$ of length $n+1$ found in $V_{g_n(m)}$ where $n=3m+|x|$. Note that $A(0)A(1)\dots A(n)$ is in the range of $M$ whenever $n > f(m)$. As the corresponding $1^m 0x$ has the length $(n+1)-2m$, it follows that $C(A(0)A(1)\dots A(n)) \le n-2m+O(1) \le n-m$ for almost all $m$ and all $n > f(m)$. Hence, by a suitable finite modification of $f$ one obtains condition (c).

(c) $\Rightarrow$ (d): This follows from Remark 1 and a substitution of $f$ by $\tilde{f}(m) := f(3m)$.

(d) $\Rightarrow$ (a): Again, by the Counting Theorem 2 there is a constant $c$ such that for every $n, m$ there are at most $2^{n-m+c}$ strings $\sigma$ of length $n+1$ with $H(\sigma) \le$
$n + H(n) - m$. Furthermore let $f$ be given as in condition (d); in particular $H(A(0)A(1)\dots A(f(m)))$ is at most $f(m) + H(f(m)) - m$. The measure of the class of the sets $B$ with the same property is at most $2^{-m-1+c}$. It follows that the mapping of $m$ to the class of all $B$ with $H(B(0)B(1)\dots B(f(m+c))) \le f(m+c) + H(f(m+c)) - m$ is a Kurtz test relative to $K$. $\square$

Let $A$ be given such that every $A$-recursive function is majorised by a $K$-recursive one. Then the above characterisations show that $A$ is strongly random iff $A$ is Kurtz random relative to $K$. But this coincidence does not hold in general as 2-generic sets are Kurtz random relative to $K$ but not strongly random. It should also be noted that there is no oracle $B$ such that every set $A$ which is not strongly random satisfies that there is an $B$-recursive function $f$ with $C(A(0)A(1)\dots A(n)) \le n-m$ for all $m$ and all $n > f(m)$. Hence the condition in Theorem 5 cannot be replaced by a class of functions which is independent of the set $A$ analyzed. It should be noted that the characterisation of "Schnorr random relative to $K$" is quite similar to that one of "Kurtz random relative to $K$".

**Theorem 9.** The following are equivalent for a set $A$:

(a) $A$ is not Schnorr random relative to $K$;

(b) There is a $K$-recursive function $f$ such that for infinitely many $m$ and all $n > f(m)$ it holds that $C(A(0)A(1)\dots A(n)) \le n-m$;

(c) There is a $K$-recursive function $f$ such that for infinitely many $m$ and all $n > f(m)$ it holds that $H(A(0)A(1)\dots A(n)) \le n + H(n) - m$.

*Proof.* (a) ⇒ (b): Downey and Griffiths [5] showed that a set $A$ is not Schnorr random iff there is a recursive sequence of strings $\sigma_0, \sigma_1, \sigma_2, \dots$ such that infinitely many of these strings are prefixes of $A$ and $\sum_j 2^{-|\sigma_j|}$ is a finite rational number; without loss of generality let the sum be 1. This characterisation can be relativised to $K$ by taking the sequence to be $K$-recursive. Now one can choose a $K$-recursive sequence $n_0, n_1, \dots$ of indices such that for each $m$ it holds that $\sum_{\ell \ge n_m} 2^{-|\sigma_\ell|} \le 2^{-3m}$; this $n_m$ can be found as the first number with $\sum_{\ell<n_m} 2^{-|\sigma_\ell|} > 1 - 2^{-3m}$. Note that the measure of each subsum $\sum_{\ell=n_m, n_m+1, \dots, n_{m+1}} 2^{-|\sigma_\ell|}$ is also bounded by $2^{-3m}$. Now one can define a plain machine $M$ such that $M(1^m 0 \tau)$ is the $\tau$-th string of length $|\tau| + 3m$ which extends one of the finitely many strings $\sigma_{n_m}^t, \sigma_{n_m+1}^t, \dots, \sigma_{n_{m+1}}^t$, where $t = |\tau| + 3m$ and $\sigma_n^s$ is the value of $\sigma_n$ after $s$ steps in some recursive approximation of the sequence. When approximating $n_m, n_{m+1}$ and the strings $\sigma_{n_m}, \sigma_{n_m+1}, \dots, \sigma_{n_{m+1}}$, there is a $K$-recursive function $f$ such that $f(m)$ is an upper bound on the time which is necessary to converge to the correct values; furthermore, one can choose $f(m)$ to be also an upper bound on $|\sigma_\ell| + 3m$ for each of these strings. It follows that for each string $\eta$ of length at least $f(m)$ there is a string $\tau$ of length $|\eta| - 3m$ such that $M(1^m 0 \tau) = \eta$; hence the plain Kolmogorov complexity of all of these strings $\eta$ is at most $|\eta| + c - 2m$ for some constant $c$. As there are infinitely many $m$ such that one of the $\sigma_\ell$ with $n_m \le \ell \le n_{m+1}$ is a prefix of $A$, it follows that there are infinitely many $m$ such that for all $n \ge f(m)$ it holds that $C(A(0)A(1)\dots A(n)) \le n - m$.
(b) ⇒ (c): This follows from Remark 1 and a substitution of $f$ by $\tilde{f}(m) := f(3m)$.

(c) ⇒ (a): Let $S_m^{c'} := \{B: H(B(0) \dots B(f(m+c')) \le f(m+c') + H(m+c') - m\}$. The Counting Theorem 2 yields a $c'$ such that $(S_m^{c'})_{m \in \omega}$ can be enlarged to a total Solovay test (as defined by Downey and Griffiths [5]) relative to $K$. This test covers $A$, so $A$ is not Schnorr random relative to $K$. $\square$

### 3 Characterising Demuth Randomness

Demuth has defined in the context of analysis a randomness notion which was formalised as follows in the framework of algorithmic randomness [13, Definition 3.6.24].

**Definition 10.** In the following let $V_0, V_1, V_2, \dots$ be an acceptable numbering of all r.e. open classes. Now one says that a set $A$ is Demuth random iff there is no $\omega$-r.e. function $f$ such that $\mu(V_{f(m)}) \le 2^{-m}$ for all $m$ and $A \in V_{f(m)}$ for infinitely many $m$.

**Theorem 11.** The following are equivalent for a set $A$:

(a) $A$ is not Demuth random;

(b) There exist $\omega$-r.e. functions $g$ and $h$ such that $A \in V_{g(m),h(m)}$ for infinitely many $m$ and $\mu(V_{g(m),h(m)}) \le 2^{-m}$ for all $m$;

(c) There exists an $\omega$-r.e. function $k$ such that for infinitely many $m$ and all $n \ge k(m)$ it holds that $C(A(0)A(1) \dots A(n)) \le n - m$;

(d) There exists an $\omega$-r.e. function $\tilde{k}$ such that for infinitely many $m$ and all $n \ge \tilde{k}(m)$ it holds that $H(A(0)A(1) \dots A(n)) \le n + H(n) - m$.

*Proof.* (a) ⇒ (b): Let $f$ be the $\omega$-r.e. function witnessing that $A$ is not Demuth random. Now define a function $\tilde{h}(e, m)$ such that $\tilde{h}(e, m)$ is the maximum step $s > 0$ for which there is $\ell \in \{1, 2, \dots, 2^m - 1\}$ with $\mu(V_{e,s-1}) \le \ell \cdot 2^{-m} < \mu(V_{e,s})$; if no such step exists then $\tilde{h}(e, m) = 0$ and $V_{e,0} = \emptyset$. Note that $\mu(V_e) - \mu(V_{e,\tilde{h}(e,m)}) \le 2^{-m}$. Given $f, \tilde{h}$, consider a function $g$ such that

$$V_{g(m)} = \bigcup_{\ell=0,1,\dots,m,m+1} (V_{f(\ell),\tilde{h}(f(\ell),2m+4-\ell)} - V_{f(\ell),\tilde{h}(f(\ell),2m+2-\ell)})$$

and the function $h$ defined by

$$h(m) = \max\{\tilde{h}(f(\ell), 2m + 4 - \ell) : \ell \in \{0, 1, \dots, m, m + 1\}\}.$$

Without loss of generality we may assume $V_{g(m)} = V_{g(m),h(m)}$. Furthermore,

$$\mu(V_{f(\ell),\tilde{h}(f(\ell),2m+4-\ell)} - V_{f(\ell),\tilde{h}(f(\ell),2m+2-\ell)}) \le \mu(V_{f(\ell)} - V_{f(\ell),\tilde{h}(f(\ell),2m+2-\ell)}) \\ \le 2^{\ell-2m-2}$$

and therefore $\mu(V_{g(m)}) \le 2^{-m-1} + 2^{-m-2} + \dots + 2^{-2m-2} \le 2^{-m}$. It remains to show that $g$ and $h$ are $\omega$-r.e. and that $A \in V_{g(m)} = V_{g(m),h(m)}$. As $f$ and
$\tilde{h}$ are both $\omega$-r.e. and $\tilde{h}(e, m)$ makes at most $2^m$ mind changes, the functions $g$ and $h$ are also $\omega$-r.e. functions. Now consider any $i$. Then there is $j > i + 1$ such that $A \in V_{f(j)}$. It follows that there is an $m \ge j - 1$ such that $A \in V_{f(j), \tilde{h}(f(j), 2m+4-j)} - V_{f(j), \tilde{h}(f(j), 2m+2-j)}$; the reason is that $\mu(V_f(j)) \le 2^{-j}$ and thus $\tilde{h}(f(j), 2m+2-j) = 0$ for $m \le j-1$. Now $V_{g(m)}$ contains $A$ and $m > i$. Hence there are infinitely many $m$ with $A \in V_{g(m), h(m)}$. So (b) holds.

(b) $\Rightarrow$ (c): Let $g, h$ be given as required in (b) and assume that $g_s(m) \neq g_{s+1}(m) \lor h_s(m) \neq h_{s+1}(m)$ implies that $h_{s+1}(m) \geq s+1$. Otherwise one can without loss of generality modify $g$ and $h$ accordingly while preserving (b). Now let $M(1^m 0x)$ be the $x$-th string found in $\{0,1\}^s$ such that $s = |x| + 3m$ and $M(1^m 0x) \cdot \{0,1\}^\infty \subseteq V_{g_s(3m),s} \cup V_{g_s(3m+1),s} \cup V_{g_s(3m+2),s}$. For infinitely many $m$ and all $n > \max\{h(3m), h(3m+1), h(3m+2)\}$ it holds that $A(0)A(1)\dots A(n) \cdot \{0,1\}^\infty \subseteq V_{g(3m)} \cup V_{g(3m+1)} \cup V_{g(3m+2)}$. For such $m, n$ there are only $2^{n+1-3m}$ strings of length $n$ qualifying for the search condition, hence there is an $x$ of length $n+1-3m$ such that $M(1^m 0x) = A(0)A(1)\dots A(n)$ and — if $m$ is furthermore large enough — $C(A(0)A(1)\dots A(n)) \le n-m$. Hence one can choose $k$ to be a finite variant of the $\omega$-r.e. function $m \mapsto \max\{h(3m), h(3m+1), h(3m+2)\} + 1$ in order to satisfy condition (c).

(c) $\Rightarrow$ (d): This follows from Remark 1 by choosing $\tilde{k}(m) := k(3m)$.

(d) $\Rightarrow$ (a): Let $\tilde{k}$ be as in condition (d). There is a function $f$ defining the class $V_{f(m)} = \{B : H(B(0)B(1)\dots B(\tilde{k}(2m))) \le \tilde{k}(2m) + H(\tilde{k}(2m)) - 2m\}$.

Note that $V_{f(m)}$ has at most measure $2^{-m}$ for almost all $m$ and we can assume that $V_{f(m)}$ contains $A$ for infinitely many $m$ (otherwise we can replace $\tilde{k}$ by the function $n \mapsto \tilde{k}(n+1)$). Furthermore, there is a recursive function which maps each triple $(m, a, b)$ to an index for the class $\{B : H(B(0)B(1)\dots B(a)) \le a+b-2m\}$ and therefore maps $(m, \tilde{k}(2m), H(\tilde{k}(2m)))$ to $f(m)$. There is a recursive function $\tilde{k}$ such that the approximation of $\tilde{k}(m)$ makes at most $\tilde{k}(m)$ mind changes. As one can code $m$ and the number of mind changes in order to get $\tilde{k}(m)$, for almost all $m$, the value $H(\tilde{k}(m))$ is at most $\tilde{k}(m)+m$ and once the value $\tilde{k}(m)$ has stabilised, $H(\tilde{k}(m))$ can be approximated from above with $\tilde{k}(m) + m$ many mind changes. It follows that the mapping $m \mapsto (\tilde{k}(2m), H(\tilde{k}(2m)))$ is $\omega$-r.e. with the number of mind changes bounded by $(\tilde{k}(2m) + 2m)^2$ for almost all $m$. Hence the function $f$ can be taken to be $\omega$-r.e. as well. Then, after a finite modification which preserves $f$ to be $\omega$-r.e., one has that not only for almost all $m$ but indeed for all $m$ the measure of $V_{f(m)}$ is bounded by $2^{-m}$. So $A$ is not Demuth random. $\square$

## 4 Characterising Turing-incomplete Martin-Löf random sets

Recall that a set $A$ is PA-complete iff there is an $A$-recursive consistent and complete extension of Peano Arithmetic. This condition is equivalent to saying that every partial-recursive $\{0,1\}$-valued function has a total $A$-recursive extension. Stephan [21] showed that a Martin-Löf random set is Turing above $K$ iff it is
PA-complete. This showed that the Martin-Löf random sets fall into two classes: those above K which coincide with the PA-complete ones and those not above K which coincide with the PA-incomplete ones. The next result shows that the PA-incomplete Martin-Löf random sets have a natural characterisation in terms of initial segment complexity. Note that all Demuth random and all strongly random sets are PA-incomplete. On the other hand, there are Martin-Löf random sets which are PA-complete like Chaitin's Ω. Gács [6] and Kučera [7] showed that every a ≥T K contains a Martin-Löf random set and those are PA-complete.

**Theorem 12.** The following statements are equivalent for a set A:

(a) A is PA-complete or A is not Martin-Löf random;

(b) A ≥T K or A is not Martin-Löf random;

(c) There is an A-recursive function f such that $C(A(0)A(1)...A(n)) ≤ n - m$ for all m and all n > f(m);

(d) There is an A-recursive function f such that $H(A(0)A(1)...A(n)) ≤ n + H(n) - m$ for all m and all n > f(m).

*Proof.* (a) ⇔ (b) is already known [21] and (c) ⇒ (d) follows from Remark 1.

(b) ⇒ (c): If A is not Martin-Löf random, the construction of f is straightforward, using the fact that A has 2m-compressible prefixes for each m.

If $K ≤_T A$, then if A were Martin-Löf random relative to K, K would be a base for ML-randomness. By [13, Theorem 5.1.22] we would have $K ∈ Low(MLR)$, a contradiction. So A is not Martin-Löf random relative to K and by Theorem 6 there is an $A ⊕ K$-recursive function f with

$$ \forall m \forall n > f(m) [C(A(0)A(1)...A(n)) ≤ n - m]. $$

By assumption, this function f is also A-recursive and satisfies the claim.

(d) ⇒ (b): Assume that $A \not\supseteq_T K$ as otherwise there is nothing to prove. Let f be as in condition (d) and let U be the universal prefix-free machine that defines H. The function $m \mapsto f(2m)$ is A-recursive and does not majorise the function

$$ g: m \mapsto \max\{U(\tau) : \tau \in \text{dom}(U) \cap \{0, 1\}^m\}, $$

since $A \not\supseteq_T K$ and only oracles Turing above K can compute functions which majorise g. Hence there are infinitely many m where the largest value $U(\tau)$ for $\tau \in \text{dom}(U) \cap \{0, 1\}^m$ is beyond $f(2m)$. By assumption on f and $\tau$,

$$ H(A(0)A(1)...A(U(\tau))) ≤ U(\tau)+H(U(\tau))-2m ≤ U(\tau)+|\tau|-2m = U(\tau)-m. $$

This shows that A is not Martin-Löf random. □

Stephan and Wu [22] called a set A strongly Kurtz random iff there is no recursive function f such that $H(A(0)A(1)...A(f(m))) ≤ f(m) - m$ for all m. Applying similar methods as above this can be generalized as follows.
**Theorem 13.** The following are equivalent for a set A:

(a) A is not strongly Kurtz-random;

(b) There is a recursive function g such that $C(A(0)A(1)...A(n)) \le n-m$ for all $m$ and all $n > g(m)$;

(c) There is a recursive function h such that $H(A(0)A(1)...A(n)) \le n+H(n)-m$ for all $m$ and all $n > h(m)$.

# 5 Conclusion and Future Work

The overall idea of this article is to measure the degree of randomness of a set A by analyzing the function

$$R^A(m) = \min\{k \in \mathbb{N} \cup \{\infty\} : \forall n [k < n < \infty \Rightarrow C(A(0)A(1)...A(n)) \le n-m]\}.$$

Note that $R^A(m) \le R^A(m+1)$ for all $m$ and that A is Kolmogorov random iff $R^A$ assumes the value $\infty$ on some inputs. One can now reformulate the main results of the paper in terms of the function $R^A$. For example, A is strongly random iff there are no $f \le_T A$ and no $g \le_T K$ such that the concatenation $n \mapsto f(g(n))$ dominates $R^A$. Here $f$ dominates $g$ iff $f(m) \ge g(m)$ for almost all $m \in \mathbb{N}$. The other results in this article can be formulated analogously in an obvious way.

When looking at $R^A$, one could define a new reducibility as follows.

**Definition 14.** A set A is said to be Kurtz-Kolmogorov-reducible to B ($A \le_{KK} B$) if there is a recursive function $f$ and a constant $c$ such that for all $m \in \mathbb{N}$ it holds that $R^A(m) \le f(R^B(m+c))$. Here, $f$ is extended to $\mathbb{N} \cup \{\infty\}$ by letting $f(\infty) = \infty$, where the conventions $\infty \le \infty$ and $\infty \not\le n$ hold for all $n \in \mathbb{N}$.

Note that this definition is invariant under recursive permutations $g$, so if $B = \{g(n) : n \in A\}$ then $A \equiv_{KK} B$. Also, it holds that all sets A, B satisfy $A \oplus B \le_{KK} A$. This meets the intuition that a sequence can become more random but not less random by omitting half of the bits.

Besides this, it can be seen that the following classes are closed upward under KK-reducibility (that is, whenever A is in the class and $A \le_{KK} B$ then also B is in the class): the class of all Kolmogorov random sets (as it consists of the greatest KK-degree); the class of all strongly Kurtz random sets (as it consists of all degrees except the least one); the class of all Demuth random sets; the class of all sets which are Kurtz random relative to K; the class of all sets which are Schnorr random relative to K.

The reason is that for all of these classes, the randomness notion is defined by comparing the growth rate of $R^A$ with that of a certain list of functions which do not depend on A.

Somehow, for the classes $\{A : A$ is strongly random$\}$ and $\{A : A$ is Martin-Löf random and $A \not\ge_T K\}$, A becomes involved and the upward closure is no longer guaranteed. Indeed, it would be interesting to know whether the role of A could be replaced by something else, so that one or both of the mentioned classes would
be closed upward with respect to KK-reducibility. Another topic for study could
be the properties of KK-reducibility and its interactions with other reducibilities.

**Acknowledgements.** The authors want to thank Laurent Bienvenu and Wolfgang Merkle for fruitful discussions and ideas used in this paper.

References

1. Bienvenu, L., Merkle, W.: Reconciling Data Compression and Kolmogorov Complexity. International Colloquium on Automata, Languages and Programming (ICALP 2007). LNCS, vol. 4596, pp. 643–654. Springer, Heidelberg (2007).

2. Calude, C.S.: Information and Randomness. An Algorithmic Perspective. Second Edition. Springer, Heidelberg (2002).

3. Chaitin, G.J.: A theory of program size formally identical to information theory. Journal of the ACM 22, 329–340 (1975).

4. Downey, R., Nies, A., Weber, R., Yu, L.: Lowness and $Π_2^0$ Nullsets. Journal of Symbolic Logic 71, 1044–1052 (2006).

5. Downey, R., Griffiths, E.: On Schnorr randomness. Journal of Symbolic Logic 69, 533–554 (2004).

6. Gács, P.: Every sequence is reducible to a random one. Information and Control 70, 186–192 (1986).

7. Kučera, A.: Measure, $Π_1^0$-classes and complete extensions of PA. Recursion Theory Week. LNM, vol. 1141, pp. 245–259. Springer, Heidelberg (1985).

8. Kurtz, S.A.: Randomness and genericity in the degrees of unsolvability. PhD dissertation, University of Illinois at Urbana-Champaign (1981).

9. Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Third Edition. Springer, Heidelberg (2008).

10. Martin-Löf, P.: The definition of random sequences. Information and Control 9, 602–619 (1966).

11. Miller, J.S.: Every 2-random real is Kolmogorov random. Journal of Symbolic Logic 69, 907–913 (2004).

12. Miller, J.S.: The *K*-degrees, low for *K* degrees and weakly low for *K* oracles. Notre Dame Journal of Formal Logic, to appear.

13. Nies, A.: Computability and Randomness. Oxford Science Publications (2009).

14. Nies, A., Stephan, F., Terwijn, S.A.: Randomness, relativization and Turing degrees. Journal of Symbolic Logic 70, 515–535 (2005).

15. Odifreddi, P.: Classical Recursion Theory I. North-Holland (1989).

16. Odifreddi, P.: Classical Recursion Theory II. Elsevier (1999).

17. Osherson, D., Weinstein, S.: Recognizing the strong random reals. The Review of Symbolic Logic 1, 56–63 (2008).

18. Schnorr, C.-P.: Zufälligkeit und Wahrscheinlichkeit. LNCS, vol. 218. Springer, Heidelberg (1971).

19. Schnorr, C.-P.: Process complexity and effective random tests. Journal of Computer and System Sciences 7, 376–388 (1973).

20. Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, Heidelberg (1987).

21. Stephan, F.: Martin-Löf Random and PA-complete Sets. Proceedings of ASL Logic Colloquium 2002. ASL Lecture Notes in Logic 27, 342–348 (2006).

22. Stephan, F., Wu, G.: Presentations of K-Trivial Reals and Kolmogorov Complexity. New Computational Paradigms: First Conference on Computability in Europe, CiE 2005. LNCS, vol. 3526, pp. 461–469. Springer, Heidelberg (2005).