Pointed computations and Martin-Löf randomness

Abstract

Schnorr showed that a real X is Martin-Löf random if and only if $K (X ↾_{n}) ⩾ n - c$ for some constant c and all n, where K denotes the prefix-free complexity function. Fortnow (unpublished) and Nies, Stephan and Terwijn [J. Symbolic Logic70 (2005), 515–535] observed that the condition $K (X ↾_{n}) ⩾ n - c$ can be replaced with $K (X ↾_{r_{n}}) ⩾ r_{n} - c$ , for any fixed increasing computable sequence $(r_{n})$ , in this characterization. The purpose of this note is to establish the following generalisation of this fact. We show that X is Martin-Löf random if and only if $\exists c \forall n K (X ↾_{r_{n}}) ⩾ r_{n} - c$ , where $(r_{n})$ is any fixed pointedly X-computable sequence, in the sense that $r_{n}$ is computable from X in a self-delimiting way, so that at most the first $r_{n}$ bits of X are queried in the computation of $r_{n}$ . On the other hand, we also show that there are reals X which are very far from being Martin-Löf random, but for which there exists some X-computable sequence $(r_{n})$ such that $\forall n K (X ↾_{r_{n}}) ⩾ r_{n}$ .

Keywords

Computability algorithmic randomness Kolmogorov complexity

1. Introduction

A well known result of Schnorr (see Chaitin [1]) is that Martin-Löf’s notion of algorithmic randomness from [9] can be expressed in terms of incompressibility with respect to prefix-free machines. In particular, a real X is Martin-Löf random if and only if $\exists c \forall n K (X ↾_{n}) > n - c$ , where K denotes the prefix-free complexity function. The latter condition says that there exists a constant c such that all the initial segments of X are c-incompressible (in a prefix-free sense). As reported in Downey and Hirschfeldt [3, Proposition 6.1.4], Fortnow (unpublished) and Nies, Stephan and Terwijn [11] showed that Schnorr’s characterisation remains valid if we replace the condition $\exists c \forall n K (X ↾_{n}) > n - c$ with $\exists c \forall n K (X ↾_{r_{n}}) > r_{n} - c$ , where $(r_{n})$ is any computable increasing sequence.

In this note we consider the extent to which this fact can be generalised to incomputable increasing sequences $(r_{n})$ . It is well known that there are reals which are not Martin-Löf random, yet have infinitely many 0-incompressible initial segments. Hence this characterisation does not hold for arbitrary increasing sequences $(r_{n})$ . We consider the case when $(r_{n})$ is computable from X. Our main result is that if $(r_{n})$ is computable from X in a certain restricted way, then X is Martin-Löf random if and only if $\exists c \forall n K (X ↾_{r_{n}}) > r_{n} - c$ . On the other hand we show how to construct reals X and X-computable sequences $(r_{n})$ such that the above equivalence fails, so we have $\forall n K (X ↾_{r_{n}}) ⩾ r_{n}$ but X is very far from being Martin-Löf random.

1.1. Pointed computability

Our main result is that if X computes $(r_{n})$ in a certain natural fashion, then $\exists c \forall n K (X ↾_{r_{n}}) > r_{n} - c$ is a sufficient and necessary condition for the Martin-Löf randomness of X. In this section we formalise the notion of oracle-computability required in order for this equivalence to hold, which we call pointed computability.

A Turing functional Φ can be thought of as a machine which takes as inputs a number n and a program σ, and either halts on these inputs producing a number $Φ^{σ} (n)$ as output, or else diverges. The consistency of Φ requires that if $ρ_{0} \subseteq ρ_{1}$ and $Φ^{ρ_{0}} (n) ↓$ , then the computation $Φ^{ρ_{1}} (n)$ is identical to that for $Φ^{ρ_{0}} (n)$ , yielding the same output. Then $Φ^{X} (n)$ can be defined as ${lim}_{s} Φ^{X ↾_{s}} (n)$ . Without loss of generality, given a Turing functional Φ, a string ρ and a number n, we may assume that $Φ^{ρ} (n) ↓$ implies $| ρ | ⩾ n$ and $| ρ | ⩾ Φ^{ρ} (n)$ . This is a standard convention and it is not hard to see that if $Ψ^{X} = Z$ for two reals and a Turing functional Ψ which might not obey the convention, then there exists a Turing functional Φ which does obey the stated convention and for which $Φ^{X} = Z$ .

Given a Turing functional Φ, a number n and strings $ρ_{0}, ρ_{1}$ , the consistency property says that if $Φ^{ρ_{0}} (n) \neq Φ^{ρ_{1}} (n)$ then we must have that $ρ_{0} ∣ ρ_{1}$ , i.e. the finite oracles differ at a digit which is less than $min {| ρ_{0} |, | ρ_{1} |}$ . The following definition is based on a more stringent consistency requirement.

Definition 1.1 (Pointed computations).

Given a real X, we say that a sequence $(r_{n})$ is pointedly X-computable if $(r_{n})$ is (strictly) increasing and there exists a Turing functional Φ such that $Φ^{X ↾_{r_{n}}} (n) ↓ = r_{n}$ for each n.

The latter condition in Definition 1.1 says that some oracle Turing machine computes each $r_{n}$ from X with oracle-use bounded above by $r_{n}$ . Note that, without loss of generality, we may assume that the oracle-use in this computation is exactly $r_{n}$ .

As a typical example of pointed computations (suppressing the monotonicity requirement for now), consider an oracle machine which starts on input n by reading increasingly longer initial segments of the oracle tape, and eventually stops after $s > n$ steps, with output s. If, for a given X, such a machine converges for every n, then it produces a pointed computation in the sense of Definition 1.1. Another example is the settling time of a non-computable c.e. set A: let $r_{0} = 0$ and for each n let $r_{n + 1}$ be the least number which is larger than $r_{n}$ and such that $A_{s} ↾_{n} = A ↾_{n}$ for all $s ⩾ r_{n + 1}$ . Then $(r_{i})$ is pointedly A-computable and non-computable.

Later we will note that there are weaker notions of computability which suffice for our characterization of Martin-Löf randomness. One such notion is the condition that $K (r_{n} ∣ τ) = O (1)$ for all n and all $τ \supseteq X ↾_{r_{n}}$ . Note that the latter is the non-uniform version of the notion of Definition 1.1.

1.2. Our results

Our main result is the following, which we prove in Section 2.

Theorem 1.2 (Randomness condition).

Suppose that $(r_{n})$ is pointedly computable from a real X. Then X is Martin-Löf random if and only if $\exists c \forall n K (X ↾_{r_{n}}) > r_{n} - c$ .

It is well-known that there are reals which are not Martin-Löf random, yet have infinitely many incompressible initial segments. Hence Theorem 1.2 does not hold if we simply waive the requirement that $(r_{n})$ is pointedly computable from X. One may ask, however, if Theorem 1.2 continues to hold if we merely require that $(r_{n})$ is computable from X and not that it is pointedly X-computable. It is not surprising that the latter question has a negative answer. One way to exhibit an example witnessing this fact, is to construct a real with infinitely many incompressible initial segments, which computes the halting problem and is not Martin-Löf random. Since the prefix-free complexity function is computable from the halting problem $\emptyset^{'}$ , given such an oracle X we can effectively find infinitely many t such that $K (X ↾_{t}) ⩾ t - c$ . This gives the following fact.

Proposition 1.3.
Suppose that X computes the halting problem, X is not Martin-Löf random and there exists some constant c and infinitely many n such that $K (X ↾_{n}) ⩾ n - c$ . Then X computes an increasing sequence $(r_{n})$ such that $K (X ↾_{r_{n}}) ⩾ r_{n} - c$ for all n.

In Section 3 we present two ways of constructing oracles X which have the properties mentioned in Proposition 1.3, thus establishing the following.
Theorem 1.4.
There exists a real X and an X-computable increasing sequence $(r_{n})$ , such that $r_{n} < K (X ↾_{r_{n}})$ for all n, and X is not Martin-Löf random.

Our first construction of such X involves starting from a Martin-Löf random Y which computes the halting problem, and inserting zeros at certain places, thus causing X to be non-random, while preserving its ability to calculate lengths at which its initial segments have high prefix-free complexity. The second construction of such an oracle X is more flexible, and gives a real which is highly non-random, in the sense that its characteristic sequence has a computable subsequence of zeros.
1.3. Related concepts and results from the literature

A central notion studied in this paper is that of a set X which is able to compute a sequence of positions in its binary expansion where the corresponding initial segments are incompressible. Clearly every Martin-Löf random has this property, but there are also many reals with this property which are not Martin-Löf random. This notion might remind some readers of the autocomplex reals (see [6,7] or [3, Section 8.16]), which are the reals X which compute a non-decreasing unbounded function f such that $K (X ↾_{n}) ⩾ f (n)$ for all n. Moreover, Theorem 1.2 has similarities to a result by Miller and Yu [10], which says that if $\sum_{i} 2^{- g (i)} < \infty$ and g is computable from X with identity oracle-use, then $\exists c \forall n K (X ↾_{n}) ⩽ n + g (n) + c$ . Note that the latter result can be seen as an extension of the following consequence of the Kraft-Chaitin inequality: $\begin{matrix} (1) & \begin{matrix} if g is computable and \sum_{i} 2^{- g (i)} < \infty then there exists a constant c such that for all \\ X and all n we have K (X ↾_{n}) ⩽ n + g (n) + c . \end{matrix} \end{matrix}$ It is clear that the result of Miller and Yu [10] is related to its special case (1) in the same way as our Theorem 1.2 is related to results originally obtained by Fortnow (unpublished) and Nies, Stephan and Terwijn [11], discussed earlier.

2. Proof of Theorem 1.2

We need to show that if $(r_{n})$ is pointedly X-computable, then X is Martin-Löf random if and only if $\exists c \forall n K (X ↾_{r_{n}}) > r_{n} - c$ .

The ‘only if’ direction in this statement is trivial, so it remains to show the ‘if’ direction. We prove the contrapositive. Assuming that X is not Martin-Löf random and $(r_{n})$ is pointedly X-computable, we show that for each constant c there exists some n such that $K (X ↾_{r_{n}}) ⩽ r_{n} - c$ . Let Φ be a Turing functional such that $Φ^{X} (n) = r_{n}$ for all n, and such that for every n, r, ρ such that $Φ^{ρ} (n) ↓ = r$ we have $Φ^{ρ ↾_{r}} (n) ↓$ , $| ρ | > n$ , $| ρ | ⩾ r$ and $Φ^{ρ} (i) ↓$ for all $i < n$ . Let U be the underlying optimal universal prefix-free machine.

We define a prefix-free machine M which makes use of the descriptions of U as follows. For each vector $(ρ, σ, n, t)$ , such that:

$Φ^{ρ} (i) ↓$ for all $i ⩽ n + 1$ and $Φ^{ρ} (i) < Φ^{ρ} (i + 1)$ for all $i < n + 1$ ;

$t \in (Φ^{ρ} (n), Φ^{ρ} (n + 1)]$ and $U (σ) = ρ ↾_{t}$ ;

let τ be the digits of ρ between digit t and digit

Φ^{ρ} (n + 1)

and note that

\begin{matrix} U (σ) * τ = ρ ↾_{Φ^{ρ} (n + 1)}, Φ^{U (σ) * τ} (n + 1) = Φ^{ρ} (n + 1) and Φ^{U (σ) * τ} (n) = Φ^{ρ} (n) . \end{matrix}

Let M describe

ρ ↾_{Φ^{ρ} (n + 1)}

with the string

σ * τ

, defining

M (σ * τ) = ρ ↾_{Φ^{ρ} (n + 1)}

. This completes the definition of M.

It follows immediately from the definition that M is effectively calculable. Next we show that M does not allocate two different strings the same description. Given two identical M-descriptions $σ_{0} * τ_{0} = σ_{1} * τ_{1}$ , since U is a prefix-free machine we must have $σ_{0} = σ_{1}$ and $τ_{0} = τ_{1}$ . By the construction of M, the string described in both cases is then $U (σ_{0}) * τ_{0}$ . In a similar manner, we may show that M is a prefix-free machine. Suppose that $σ_{0} * τ_{0} \subseteq σ_{1} * τ_{1}$ are two descriptions issued by M, resulting from the vectors $(ρ_{0}, σ_{0}, n_{0}, t_{0})$ , $(ρ_{1}, σ_{1}, n_{1}, t_{1})$ respectively. Since U is a prefix-free machine and $σ_{0}$ , $σ_{1}$ are U-descriptions, we have $σ_{0} = σ_{1}$ , $t_{0} = t_{1}$ and $τ_{0} \subseteq τ_{1}$ . Let σ be $σ_{0}$ and let t be $t_{0}$ . Then $ρ_{0} \subseteq ρ_{1}$ and hence1

¹
An intuitive description of the argument that follows for showing that $τ_{0} = τ_{1}$ is this: each of $ρ_{0}, ρ_{1}$ determine a sequence $Φ^{ρ_{0}} (i)$ , $i ⩽ n_{0} + 1$ , although $ρ_{1}$ may be able to define $Φ^{ρ_{1}} (i)$ for $i > n_{0} + 1$ . However $t \in (Φ^{ρ_{0}} (n_{0}), Φ^{ρ_{0}} (n_{0} + 1)]$ so by the construction of M we have that both $τ_{0}$ , $τ_{1}$ equal the digits of $ρ_{0}$ (or equivalently $ρ_{1}$ ) between digit t and digit $Φ^{ρ_{0}} (n_{0} + 1)$ .

\begin{matrix} (2) & Φ^{ρ_{0}} (n_{0} + 1) = Φ^{U (σ) * τ_{0}} (n_{0} + 1) = Φ^{U (σ) * τ_{1}} (n_{0} + 1) = Φ^{ρ_{1}} (n_{0} + 1) . \end{matrix}

Thus

(Φ^{ρ_{0}} (n_{0}), Φ^{ρ_{0}} (n_{0} + 1)] = (Φ^{ρ_{1}} (n_{0}), Φ^{ρ_{1}} (n_{0} + 1)]

, and t belongs to both intervals. This means that

n_{0} = n_{1}

, because otherwise

t_{1}

would have to belong to a different interval, not the one determined by

n_{0}

and

ρ_{1}

, since the values of Φ are strictly monotone. This would be a contradiction by the choice of

(ρ_{1}, σ_{1}, n_{1}, t_{1})

in the definition of M and the fact that

t_{0} = t_{1}

which was established earlier. So let

n = n_{0} = n_{1}

. Since

U (σ) * τ_{0} = ρ_{0} ↾_{Φ^{ρ_{0}} (n + 1)}

and

U (σ) * τ_{1} = ρ_{1} ↾_{Φ^{ρ_{1}} (n_{0} + 1)}

, by (2) the strings

U (σ) * τ_{0}

U (σ) * τ_{1}

have the same length, so

τ_{0} = τ_{1}

, which shows that the two descriptions

σ_{0} * τ_{0}

σ_{1} * τ_{1}

are identical. This completes the proof that M is a prefix-free machine.

It remains to show that if X is not Martin-Löf random, then for each c there exists some n with $K (X ↾_{r_{n}}) ⩽ r_{n} - c$ . Let d be a constant such that $K (η) ⩽ K_{M} (η) + d$ for all strings η. Given any constant c, since X is not Martin-Löf random, there exists some $t > 0$ such that $K (X ↾_{t}) ⩽ t - c - d$ . Let n be such that $t \in (r_{n}, r_{n + 1}]$ . Then M will describe $X ↾_{r_{n + 1}}$ with $σ * τ$ where σ is the shortest description of $X ↾_{t}$ and the length of τ is $r_{n + 1} - t$ . The length of σ is $K (X ↾_{t})$ , which is at most $t - c - d$ . We have: $\begin{matrix} K_{M} (X ↾_{r_{n + 1}}) ⩽ (t - c - d) + (r_{n + 1} - t) = r_{n + 1} - c - d . \end{matrix}$ So $K (X ↾_{r_{n + 1}}) ⩽ r_{n + 1} - c$ , as required.

3. Proof of Theorem 1.4

As discussed in the introduction, we present two different constructions of a real X which computes an increasing sequence $(r_{n})$ such that $K (X ↾_{r_{n}}) > r_{n}$ for all n and X is not Martin-Löf random.

3.1. An ad hoc construction

One way to construct a real X with the property of Proposition 1.3 is to start from a Martin-Löf random real Y which computes the halting problem, and insert zeros into Y in a way that does not change the fact that $\emptyset^{'}$ is computable from the resulting oracle, but does ensure non-randomness. Recall that a Martin-Löf random real Y which computes the halting problem exists by the Kučera–Gács theorem [5,8]. In this construction we use the result of Chaitin [1], which asserts that: $\begin{matrix} (3) & \begin{matrix} if Z is Martin-Löf random then {lim}_{s} (K (Z ↾_{s}) - s) = \infty . \end{matrix} \end{matrix}$ We also use the fact that for each real Z which is Martin-Löf random and each string σ, the real $σ * Z$ is Martin-Löf random, and the fact from [2] that: $\begin{matrix} (4) & \begin{matrix} if Z is Martin-Löf random and f is a partial computable function on strings, then if f (Z ↾_{n}) ↓ \\ for infinitely many n, there are infinitely many t such that f (Z ↾_{t}) ↓ \neq Z (t) . \end{matrix} \end{matrix}$ The reader may observe that a partial computable prediction rule f as above which is always successful on Z would give rise to a computable martingale which succeeds on Z, which we know is not possible for Martin-Löf random reals (e.g. see [3, Section 6.3]).

Let Φ be a functional via which Y computes the complexity function K, i.e. such that $Φ^{Y} (σ) = K (σ)$ for all σ. We form X from Y by inserting 0s at various positions, in a stage by stage process. The real X is defined as the limit of a sequence $X_{s}$ and we form each $X_{s + 1}$ from $X_{s}$ by inserting a 0 at position $t_{s + 1}$ , which means that we define $X_{s + 1} (n) = X_{s} (n)$ for $n < t_{s + 1}$ , $X_{s + 1} (n) = 0$ for $n = t_{s + 1}$ and $X_{s + 1} (n + 1) = X_{s} (n)$ for $n ⩾ t_{s + 1}$ . At stage 0 we define $X_{0} = Y$ , and (for convenience) define $t_{0} = - 1$ . Now inductively suppose that we have performed stages $0, \dots, k$ , and that we have recorded $t_{0}, \dots, t_{k}$ . For any string $τ \subset X_{k}$ , let $τ^{*}$ be the string which results from removing all of the 0s that we have inserted during the stages $⩽ k$ . At step $k + 1$ we search for $σ \subset X_{k}$ of $length > t_{k} + 2$ and $τ \subset X_{k}$ with $σ \subset τ$ such that $Φ^{τ^{*}}$ computes $K (σ)$ and $K (σ) > | σ |$ . By (3), it follows that such σ and τ exist. Then we define $t_{k + 1} = | τ |$ and insert a 0 at position $t_{k + 1}$ .

This completes the construction of X given Y. From the construction it follows that X computes both Y and the sequence $(t_{k})$ . This follows because X is able to retrace the construction. Inductively suppose that X has been able to retrace the construction up until the end of stage k, and so knows the values $t_{0}, \dots, t_{k}$ . Then, using the oracle for X we can perform the same search that was carried out at stage $k + 1$ , but using X rather than $X_{k}$ : we search for $σ \subset X$ of $length > t_{k} + 2$ and $τ \subset X$ with $σ \subset τ$ such that $Φ^{τ^{*}}$ computes $K (σ)$ and $K (σ) > | σ |$ . Since the next zero is inserted after τ, the result of the search is the same as when $X_{k}$ was used during the construction at stage $k + 1$ . Then $t_{k + 1} = | τ |$ , completing the induction step. Therefore X computes the halting set $\emptyset^{'}$ . Moreover there is a partial computable function f such that for each $σ \subset X$ we have $f (σ) ↓$ if and only if $σ = X ↾_{t_{k}}$ for some k (f uses σ as an oracle to try and retrace the construction and converges on σ if it is of length $t_{k}$ for some k in the retraced construction). For each k, the next digit $t_{k}$ of X is a 0, so f is a partial computable prediction rule that succeeds on X, which means that X is not Martin-Löf random. This completes the construction of a set X with the properties of Proposition 1.3.

3.2. A refined construction

Here we construct the required X by finite extensions. This construction can be combined with other requirements. For example, X can be highly non-random, in the sense that it has a computable sequence of 0s. We need some facts from the theory of prefix-free Kolmogorov complexity. For each string σ, let $σ^{*}$ denote the shortest prefix-free description of σ (if there are many shortest descriptions, we consider the one which describes σ first). Also let $K (τ ∣ ρ)$ denote the prefix-free complexity of τ relative to string ρ. The following is a relativized version of Chaitin’s counting theorem from [1].

Lemma 3.1 (Relativized counting theorem).

There exists a constant c such that for all σ, r and all $n > σ$ : $\begin{matrix} | {τ | σ \subseteq τ \land τ \in 2^{n} \land K (τ ∣ σ^{*}) ⩽ | τ | - r - K (σ)} | ⩽ 2^{n - K (σ) + c - r - K (n ∣ σ^{*})} . \end{matrix}$

Proof.
Given σ we define $F (n ∣ σ^{})$ for $n > | σ |$ to be the $- log$ of the weight of the prefix-free descriptions relative to $σ^{}$ which describe extensions of σ of length n. Then since the relative prefix-free complexity K is a minimal information measure, there exists a constant c such that for all n, σ, $\begin{matrix} (5) & 2^{- F (n ∣ σ^{})} < 2^{- K (n ∣ σ^{}) + c} . \end{matrix}$ We claim that the constant c has the property of the statement of the lemma. For a contradiction, suppose that this is not the case. Then for some n there are more than $2^{n - K (σ) + c - r - K (n ∣ σ^{})}$ many τ such that $K (τ ∣ σ^{}) ⩽ | τ | - r - K (σ)$ . In that case we have $\begin{matrix} 2^{- F (n ∣ σ)} > 2^{n - K (σ) + c - r - K (n ∣ σ^{})} \cdot 2^{- n + r + K (σ)} = 2^{c - K (n ∣ σ^{})}, \end{matrix}$ which contradicts (5). This contradiction concludes the proof of the lemma. □

Recall the symmetry of information fact from [1,4]: $\begin{matrix} K (τ) + K (σ ∣ τ^{}) = K (σ) + K (τ ∣ σ^{}) + Ω (1) \end{matrix}$ where $f = g + Ω (1)$ for two functions f, g means that $| f (n) - g (n) |$ is bounded above. Since $K (τ) = K (σ, τ) + O (1)$ for all strings σ, τ, by the symmetry of information, Lemma 3.1 has the following corollary.
Corollary 3.2 (Relativized counting, again).

There exists a constant c such that $\begin{matrix} | {τ | σ \subseteq τ \land τ \in 2^{n} \land K (τ) ⩽ | τ | - r} | ⩽ 2^{n - K (σ) + c - r - K (σ ∣ τ^{*}) - K (n ∣ σ^{*})} \end{matrix}$ for all $σ, r$ and all $n > σ$ .

Corollary 3.2 is the tool we are going to use for our finite extension construction. The problem we face is, given a string σ to find an extension τ such that $K (τ) > | τ |$ . Since there are $2^{n - | σ |}$ many extensions of σ of length n, by Corollary 3.2 it suffices to consider n such that $2^{n - K (σ) + c - K (n ∣ σ^{*})} < 2^{n - | σ |}$ , which means that $| σ | + c < K (σ) + K (n ∣ σ^{*})$ so $\begin{matrix} K (n ∣ σ^{*}) > | σ | - K (σ) + c . \end{matrix}$ Such a number n clearly exists in the interval $[| σ |, | σ | + 2^{c + | σ | - K (σ)}]$ . The quantity $| σ | - K (σ)$ is sometimes called the randomness deficiency of σ. We have shown that: $\begin{matrix} (6) & \begin{matrix} There exists a constant c such that each σ can be extended by less than 2^{c + | σ |} - 1 \\ many bits to a string τ with K (τ) > | τ | . \end{matrix} \end{matrix}$ We are ready to construct the required real X by finite extensions $\begin{matrix} (7) & ρ_{0} \subset τ_{1} \subset ρ_{1} \subset τ_{2} \subset \dots \end{matrix}$ In this construction the lengths $ℓ_{i} : = | τ_{i} |$ will be computable while the strings $ρ_{i}$ will be chosen so that $K (ρ_{i}) > | ρ_{i} |$ for all i. For each i the string $τ_{i + 1}$ will be the concatenation of $ρ_{i}$ with a string $10 \dots 0$ such that $| τ_{i} | = ℓ_{i}$ . So for each i the string $ρ_{i}$ will be uniformly computable from $τ_{i}$ : simply find the first 1 starting from position $| τ_{i} |$ in $τ_{i}$ and moving to the left, and if this 1 is at position t then $ρ_{i} = τ_{i} ↾_{t}$ . Let c be the constant in (6).

Let $ρ_{0}$ be the empty string λ, so that $K (ρ_{0}) > | ρ_{0} |$ . Let $τ_{1}$ be the string $ρ_{0} * 10$ and let $ℓ_{1} = | ρ_{0} | + 2 = 2$ . Note that the last digit of $τ_{1}$ is a 0. By (6) there exists an extension $ρ_{1}$ of $τ_{1}$ such that $| ρ_{1} | - | τ_{1} | < 2^{c + ℓ_{1}} - 1$ and $K (ρ_{1}) > | ρ_{1} |$ . Then let $τ_{2}$ be the concatenation of $ρ_{1}$ with a string $10 \dots 0$ such that the length $ℓ_{2} : = | τ_{2} |$ is $ℓ_{1} + 2^{c + ℓ_{1}}$ . Note that $τ_{2}$ is longer than $ρ_{1}$ by at least 2 bits, so the last digit of $τ_{2}$ is a 0. Similarly, we can choose an extension $ρ_{2}$ of $τ_{2}$ of less than $2^{c + ℓ_{2}} - 1$ many additional bits such that $K (ρ_{2}) > | ρ_{2} |$ . As before we let $τ_{3}$ be the concatenation of $ρ_{2}$ with a string $10 \dots 0$ such that the length of $τ_{3}$ is $ℓ_{3} : = ℓ_{2} + 2^{c + ℓ_{2}}$ . Note that $τ_{3}$ is longer than $ρ_{2}$ by at least 2 bits, so the last digit of $τ_{3}$ is a 0.

The construction continues similarly, thus defining the computable sequence of lengths $ℓ_{n + 1} = ℓ_{n} + 2^{c + ℓ_{n}}$ for each $n > 0$ , where $ℓ_{1} = 2$ , and the sequences (7) such that for all $i > 0$ we have $K (ρ_{i}) > | ρ_{i} |$ , $| τ_{i} | = ℓ_{i}$ and the last digit of $τ_{i}$ is 0. If we let X be the infinite extensions of the strings (7) then we have $X (ℓ_{i} - 1) = 0$ for all i, so X is not Martin-Löf random. On the other hand $X ↾_{ℓ_{i}} = τ_{i}$ for all i, and since $τ_{i}$ uniformly computes $ρ_{i}$ , we have that the sequence $(| ρ_{i} |)$ is X-computable. Finally $K (X ↾_{| ρ_{i} |}) = K (ρ_{i} |) > | ρ_{i} |$ for all i, which concludes the verification of the required properties of X.

4. Conclusion and discussion

We have generalized the criterion for Martin-Löf randomness by Fortnow (unpublished) and Nies, Stephan and Terwijn [11], which says that if X has incompressible segments of a computable sequence of lengths $(r_{n})$ , then it is Martin-Löf random. We proved that the condition that $(r_{n})$ is computable can be replaced by the weaker condition that $(r_{n})$ is pointedly X-computable, in the sense that $r_{n}$ is uniformly computable from any extension of $X ↾_{r_{n}}$ . It is a simple exercise to extend our proof of this fact in order to replace the condition of pointed computation with a non-uniform version of it, namely that $K (r_{n} ∣ τ) = O (1)$ for all n and all $τ \supseteq X ↾_{r_{n}}$ . On the other hand, we showed that this condition is no longer sufficient for Martin-Löf randomness, if we merely require that $r_{n}$ be computable from X. It would be interesting to refine this analysis and find exactly what kind of computations are allowed of a sequence $(r_{n})$ from an oracle X such that the Martin-Löf randomness of X is equivalent to the segments $X ↾_{r_{n}}$ being incompressible.

Footnotes

Acknowledgements

Barmpalias was supported by the 1000 Talents Program for Young Scholars from the Chinese Government, grant no. D1101130. Additional support was received by the Chinese Academy of Sciences (CAS) and the Institute of Software of the CAS. Lewis-Pye was supported by a Royal Society University Research Fellowship. Angsheng Li was partially supported by the National Basic Science Program (973 Program Group) entitled Cyber Information and Computational Theory on Big Data with Grant No. 2014CB340302.

References

G.J.

Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach.22 (1975), 329–340. doi:10.1145/321892.321894.

G.J.

Chaitin, Incompleteness theorems for random reals, Advances in Applied Mathematics8 (1987), 119–146. doi:10.1016/0196-8858(87)90010-8.

R.G.

Downey and

Hirshfeldt, Algorithmic Randomness and Complexity, Springer, 2010.

Gács, The symmetry of algorithmic information, Dokl. Akad. Nauk SSSR218 (1974), 1265–1267.

Gács, Every sequence is reducible to a random one, Inform. and Control70(2–3) (1986), 186–192. doi:10.1016/S0019-9958(86)80004-3.

Kjos-Hanssen,

Merkle and

Stephan, Kolmogorov complexity and the recursion theorem, in: STACS, 2006, pp. 149–161.

Kjos-Hanssen,

Merkle and

Stephan, Kolmogorov complexity and the recursion theorem, Trans. Amer. Math. Soc.363 (2011).

Kučera, Measure,

Π_{1}^{0}

-classes and complete extensions of

PA

, in: Recursion Theory Week, Oberwolfach, 1984, Lecture Notes in Math., Vol. 1141, Springer, Berlin, 1985, pp. 245–259. doi:10.1007/BFb0076224.

Martin-Löf, The definition of random sequences, Information and Control9 (1966), 602–619. doi:10.1016/S0019-9958(66)80018-9.

10.

J.S.

Miller and

Yu, Oscillation in the initial segment complexity of random reals, Adv. Math.226(6) (2011), 4816–4840. doi:10.1016/j.aim.2010.12.022.

11.

Nies,

Stephan and

S.A.

Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic70(2) (2005), 515–535. doi:10.2178/jsl/1120224726.