2.1 Some notation

We fix the following notation and terminology. We denote the natural numbers by $\omega $ , and the set of infinite binary sequences, also known as Cantor space, by $2^\omega $ . We denote the set of finite binary strings by $2^{<\omega }$ and the empty string by $\varepsilon $ . Let $\mathbb {Q}_2$ be the set of non-negative dyadic rationals, that is, rationals of the form $m/2^n$ for $m,n\in \omega $ .

Given $X\in 2^\omega $ and an integer n, $X {\upharpoonright } n$ is the string that consists of the first n bits of X, and $X(n)$ is the $(n+1)$ st bit of X (so that $X(0)$ is the first bit of X). If $\sigma $ and $\tau $ are strings, then $\sigma \preceq \tau $ means that $\sigma $ is an initial segment of $\tau $ . Similarly, for $X\in 2^\omega $ , $\sigma \prec X$ means that $\sigma $ is an initial segment of X.

Given a string $\sigma $ , the cylinder $[\![\sigma ]\!]$ is the collection of elements of $2^\omega $ having $\sigma $ as an initial segment. Similarly, given $S\subseteq 2^{<\omega }$ , $[\![ S]\!]$ is defined to be the collection $\bigcup _{\sigma \in S}[\![\sigma ]\!]$ . The cylinders form a basis for the usual product topology on Cantor space, and thus the open sets for this topology are those of the form $[\![ S ]\!]$ for some S. An open set $\mathcal {U}$ is said to be effectively open (or $\Sigma ^0_1$ ) if $\mathcal {U}=[\![ S ]\!]$ for some computably enumerable (hereafter, c.e.) set $S \subseteq 2^{<\omega }$ . An effectively closed (or $\Pi ^0_1$ ) set is the complement of an effectively open set. A sequence of open sets $(\mathcal {U}_n)_{n \in \omega }$ is said to be uniformly effectively open if there exists a sequence $(S_n)_{n \in \omega }$ of uniformly c.e. sets of strings such that $\mathcal {U}_n=[\![ S_n ]\!]$ for all $n\in \omega $ .

For $\mathcal {A}\subseteq 2^\omega $ , we write $(\mathcal {A})^{\equiv _{\mathrm {T}} }$ for the closure of $\mathcal {A}$ under Turing equivalence; that is, we let

$$ \begin{align*}(\mathcal{A})^{\equiv_{\mathrm{T}} }:=\{X\in2^\omega\colon (\exists Y\in\mathcal{A})\;X\equiv_{\mathrm{T}} Y\}.\end{align*} $$

2.2 Turing functionals and computable measures

We assume that the reader is familiar with the basics of computability theory (for instance, the material covered in [Reference Solomonoff28, Chapters I–IV], [Reference Nies22, Chapter 1], or [Reference Dekker and Myhill9, Chapter 2]).

When $\Phi ^X\in 2^\omega $ , we will often write $\Phi ^X$ as $\Phi (X)$ to emphasize that we view the functional $\Phi $ as a (partial) map from $2^\omega $ to $2^\omega $ .

A measure $\mu $ on $2^\omega $ is computable if $\sigma \mapsto \mu ([\![\sigma ]\!])$ is computable as a real-valued function, that is, if there is a computable function $\widetilde \mu \colon 2^{<\omega }\times \omega \rightarrow \mathbb {Q}_2$ such that

$$ \begin{align*}|\mu([\![\sigma]\!])-\widetilde \mu(\sigma,i)|\leq 2^{-i}\end{align*} $$

for every $\sigma \in 2^{<\omega }$ and $i\in \omega $ . For all measures appearing in this article we assume that $\mu (2^\omega )\leq 1$ without explicit mention. From now on, we will write $\mu ([\![\sigma ]\!])$ as $\mu (\sigma )$ . By Carathéodory’s Theorem, if the values $\mu (\sigma )$ , for $\sigma \in 2^{<\omega }$ , of a measure $\mu $ on $2^\omega $ are fixed, then there is a unique extension of $\mu $ to the Borel $\sigma $ -algebra generated by the sets $[\![ \sigma ]\!]$ , for $\sigma \in 2^{<\omega }$ . In this article, all measures will be defined in this way, which implies in particular that the same sets are measurable for each of these measures.

The uniform $($ or Lebesgue $)$ measure $\lambda $ is the probability measure for which each bit of the sequence has value $0$ with probability $1/2$ , independently of the values of the other bits. It can be defined as the unique Borel measure such that $\lambda (\sigma )=2^{-|\sigma |}$ for all strings $\sigma $ . Clearly, $\lambda $ is a computable measure.

2.3 Notions of algorithmic randomness

The primary notion of algorithmic randomness that we will consider in this study is Martin-Löf randomness.

We will also consider relative versions of Martin-Löf randomness, obtained by relativizing the above notion of a Martin-Löf test to some oracle $A\in 2^\omega $ ; such a class will be written as $\mathrm {MLR}^A$ . For $A=\emptyset ^{(n)}$ , the resulting notion of randomness is known as $(n+1)$ -randomness. Other randomness notions can be obtained as follows.

Let $\mathrm {SR}$ and $\mathrm {KR}$ denote the collections of Schnorr random and Kurtz random sequences, respectively.

Each of the above notions of tests and randomness can also be formulated for arbitrary computable measures $\mu $ on $2^\omega $ simply by replacing the Lebesgue measure $\lambda $ in the respective definitions by $\mu $ . Thus, for instance, for a fixed computable measure $\mu $ , a sequence X is $\mu $ -Martin-Löf random, denoted $X\in \mathrm {MLR}_\mu $ , if and only if X is not contained in any $\mu $ -Martin-Löf test. Significantly, Martin-Löf randomness with respect to some computable measure is Turing invariant in the following sense.

The requirement that X be non-computable is necessary since every computable sequence X is random with respect to some computable measures on $2^\omega $ , for example the measure $\delta _X$ defined for $\mathcal {A} \subseteq 2^{\omega }$ via

$$ \begin{align*}\delta_X(\mathcal{A})=\begin{cases}1 & \text{if }X \in {\mathcal{A}}, \\ 0 & \text{else.} \end{cases}\end{align*} $$

3.1 Left-c.e. semi-measures

Functions satisfying conditions (i) and (ii) above are sometimes referred to in the algorithmic randomness literature as continuous semi-measures to distinguish them from discrete semi-measures. As we do not consider discrete semi-measures in this study, we will not make this distinction below.

In Section 6, the support of a semi-measure will play an important role.

Definition 3.2. The support of a semi-measure P, denoted $\mathrm {Supp}(P)$ is the collection of sequences

$$ \begin{align*} \{X\in2^\omega\colon\forall n\; P(X{\upharpoonright} n)>0\}. \end{align*} $$

It is not immediately clear how to extend semi-measures to Borel subsets of $2^\omega $ . Levin and V’yugin [Reference Levin and V’yugin19] proposed the following way of deriving measures from left-c.e. semi-measures.

Definition 3.3. Given a left-c.e. semi-measure P and $\sigma \in 2^{<\omega }$ we define

$$ \begin{align*} \overline{P}(\sigma)=\inf_n\sum_{\sigma\preceq\tau \;\wedge\; |\tau|=n}P(\tau). \end{align*} $$

$\overline {P}$ can be extended to a measure on $2^\omega $ , which we will also write as $\overline P$ , by letting $\overline {P}([\![ \sigma ]\!]) = \overline {P}(\sigma )$ and then applying Carathéodory’s theorem. One can show inductively that $\overline P$ is the maximal measure such that $\overline P(\sigma )\leq P(\sigma )$ for every $\sigma \in 2^{<\omega }$ (see, for instance, [Reference Bienvenu, Hölzl, Porter and Shafer3, Proposition 6.5]). As a consequence, $\overline {P}$ is typically not a probability measure.

Inversely, given any computable measure $\mu $ defined on $2^\omega $ , we can identify it with the left-c.e. semi-measure ${\sigma \mapsto \mu ([\![ \sigma ]\!])}$ defined on $2^{<\omega }$ ; then we have $\overline \mu =\mu $ .

An important property of left-c.e. continuous semi-measures is the following.

Using Theorem 3.4 one can derive an alternative characterization of $\overline {P}$ for any left-c.e. semi-measure P.

Proposition 3.5. Let P be a left-c.e. semi-measure. Then

$$ \begin{align*} \overline P(\sigma)=\lambda(\{X\in2^\omega\colon\Phi^X\in2^\omega\;\wedge\; \Phi^X\succeq\sigma\}), \end{align*} $$

where $\Phi $ is as in Theorem 3.4 $($ ii $)$ . Moreover, for measurable $\mathcal {A} \subseteq 2^\omega $ , Carathéodory’s theorem implies that

$$ \begin{align*}\overline P(\mathcal{A})=\lambda(\Phi^{-1}(\mathcal{A})).\end{align*} $$

For a proof of the first part of the proposition, see [Reference Bienvenu, Hölzl, Porter and Shafer3, Proposition 6.5].

Theorem 3.6 Levin and Zvonkin [Reference Levin and Zvonkin20]

There is a universal left-c.e. semi-measure, that is, a left-c.e. semi-measure M such that for every left-c.e. semi-measure P, there is some constant c such that

$$ \begin{align*} P(\sigma)\leq c\cdot M(\sigma), \end{align*} $$

for every $\sigma \in 2^{<\omega }$ .

Using a universal semi-measure we can provide an alternative characterization of $\mu $ -Martin-Löf randomness for each computable measure $\mu $ .

We can now define the notion of negligibility.

As a consequence of Remark 3.7(iii) we obtain the following corollary.

Negligibility of a collection can alternatively be characterized by stipulating that no Turing functional produce an element of that collection with positive probability, as the following proposition shows.

Proposition 3.11. Let $(\Phi _i)_{i\in \omega }$ be an effective enumeration of all Turing functionals. Then a measurable $\mathcal {B}\subseteq 2^\omega $ is negligible if and only if

$$ \begin{align*} \lambda\bigg(\bigcup_{i\in\omega}\Phi_i^{-1}(\mathcal{B})\bigg)=0. \end{align*} $$

Proof ( $\Rightarrow $ :) Suppose that $\lambda \Bigl (\bigcup _{i\in \omega }\Phi _i^{-1}(\mathcal {B})\Bigr )>0$ . Then there is some i such that $\lambda (\Phi _i^{-1}(\mathcal {B}))>0$ . Setting $P(\sigma )=\lambda ([\![ \Phi _i^{-1}(\sigma ) ]\!])$ for $\sigma \in 2^{<\omega }$ , it follows from Theorem 3.4(i) that P is a left-c.e. semi-measure. Moreover, we have $\overline P(\mathcal {B})=\lambda (\Phi _i^{-1}(\mathcal {B}))$ by Proposition 3.5 and thus $\overline P(\mathcal {B})>0$ . By Remark 3.7(iii), $\overline M(\mathcal {B})>0$ , so $\mathcal {B}$ is not negligible.

( $\Leftarrow $ :) Let $\Phi $ be a Turing functional such that $M=\lambda _\Phi $ , which exists by Theorem 3.4(ii). If $\mathcal {B}$ is not negligible, then we have $0<\overline M(\mathcal {B})=\lambda (\Phi ^{-1}(\mathcal {B}))$ by Proposition 3.5, and hence

$$ \begin{align*}\lambda\Bigl(\bigcup_{i\in\omega}\Phi_i^{-1}(\mathcal{B})\Bigr)>0.\\[-50pt] \end{align*} $$

Intuitively, a collection of sequences is negligible if none of its elements can be obtained with positive probability by any probabilistic algorithm. Indeed, we can see a probabilistic algorithm as consisting of two steps: First we generate infinitely many random bits, then we feed them to some Turing functional to produce the desired output. More formally, we can think of a probabilistic algorithm as given by applying a Turing functional $\Phi $ to some random sequence. In this case, we can probabilistically compute an element of some fixed collection $\mathcal {B}$ with positive probability if there are positive measure many sequences X such that $\Phi (X)\in \mathcal {B}$ . Proposition 3.11 tells us that the existence of such a probabilistic algorithm to compute elements of $\mathcal {B}$ with positive probability is equivalent to the non-negligibility of $\mathcal {B}$ .

We conclude this subsection with a brief discussion of the atoms of a semi-measure.

Proof ( $\Rightarrow $ :) If there is some $\delta>0$ such that $P(X{\upharpoonright } n)>\delta $ for all n, then for each n and each ${m\geq n}$ ,

$$ \begin{align*} \sum_{X{\upharpoonright} n\preceq\tau \;\wedge\; |\tau|=m}P(\tau)\geq P(X{\upharpoonright} m)>\delta. \end{align*} $$

It follows from the definition of $\overline {P}$ that $\overline {P}(X{\upharpoonright } n)>\delta $ for all n.

( $\Leftarrow $ :) ${\overline {P}(\{X\})>0}$ implies that there is a $\delta>0$ such that $\overline {P}(X{\upharpoonright } n)>\delta $ for all n. Then, for all n,

$$ \begin{align*}P(X{\upharpoonright} n)\geq \overline{P}(X{\upharpoonright} n)> \delta.\\[-36pt]\end{align*} $$

3.2 Examples of negligible and non-negligible collections

We now provide a number of examples of negligible and non-negligible collections of sequences, where the first set of examples is given by a classical theorem of Sacks.

Arbitrary subsets of $2^\omega $ of positive Lebesgue measure are further trivial examples of non-negligible collections. Thus, each of the notions of randomness defined above in Section 2.3 forms a non-negligible collection.

We can find more interesting examples by considering naturally occurring collections of Turing degrees. We briefly review some of these collections. First, a sequence has PA degree if it computes a consistent completion of Peano arithmetic. A sequence $X\in 2^\omega $ is high (or has high Turing degree) if and only if $\{X\in 2^\omega \colon X''\geq _{\mathrm {T}}\emptyset '\}$ . A sequence $X\in 2^\omega $ is 1-generic if for every c.e. $S\subseteq 2^{<\omega }$ , there is some $\sigma \prec X$ such that either $\sigma \in S$ or for all $\tau \succeq \sigma $ , $\tau \notin S$ . Similarly, $X\in 2^\omega $ is 2-generic if for every $\emptyset '$ -c.e. $S\subseteq 2^{<\omega }$ , there is some $\sigma \prec X$ such that either $\sigma \in S$ or for all $\tau \succeq \sigma $ , $\tau \notin S$ . Next, $X\in 2^\omega $ has hyperimmune-free degree if and only if every X-computable function is dominated by some computable function. Accordingly, X has hyperimmune degree if and only if X computes a function that is not dominated by any computable function. $X\in 2^\omega $ is of DNC degree if and only if there is some $f\leq _{\mathrm {T}} X$ such that $f(e)\neq \varphi _e(e)$ for all $e\in \omega $ . Lastly, X is generalized low (or is in GL $_1$ ) if and only if $X'\equiv _{\mathrm {T}} X\oplus \emptyset '$ .

To establish the negligibility or non-negligibility of the various collections given above, we will use the following heuristic principles, which are justified by Proposition 3.11.

• (P ₁) If every sufficiently random sequence computes an element of some measurable $\mathcal {B}\subseteq 2^\omega $ , then $\mathcal {B}$ is non-negligible.

• (P ₂) If no sufficiently random sequence computes an element of some measurable $\mathcal {B}\subseteq 2^\omega $ , then $\mathcal {B}$ is negligible.

4.1 Elementary properties of the $\mathrm {LV}$ -degrees

Recall that A is an atom of a Boolean algebra $\mathcal {B}$ if there are no elements $A_0$ , $A_1\in \mathcal {B}\setminus \{0\}$ such that $A=A_0\vee A_1$ and $A_0\wedge A_1=0$ . To avoid confusion with the atoms of a semi-measure, we will hereafter refer to atoms of $\mathcal {D}_{\mathrm {LV}}$ as $\mathcal {D}_{\mathrm {LV}}$ -atoms. As reported by V’yugin [Reference V’yugin33] in results attributed to Levin, two $\mathcal {D}_{\mathrm {LV}}$ -atoms are readily identifiable: the $\mathrm {LV}$ -degree of the computable sequences, denoted $\mathbf {c}$ , and the $\mathrm {LV}$ -degree of the Martin-Löf random sequences, denoted $\mathbf {r}$ . We provide the proofs of these results here.

For $\mathcal {A}\subseteq 2^\omega $ , let $\mathrm {Spec}_{\mathrm {T}} (\mathcal {A})=\{\deg _{\mathrm {T}} (X)\colon X\in \mathcal {A}\}$ be the Turing degree spectrum of $\mathcal {A}$ . The following basic fact will be useful.

Proof The statement $\mathbf {a_0}\wedge \mathbf {a_1}=\mathbf {0}$ says that if we pick any element $\mathcal {B}_0 \in \mathcal {I}$ of the equivalence class $\mathbf {a_0}$ and any element $\mathcal {B}_1 \in \mathcal {I}$ of the equivalence class $\mathbf {a_1}$ , then $\mathcal {B}_0 \cap \mathcal {B}_1$ is negligible. Then $\mathcal {A}_0 := \mathcal {B}_0 \setminus \mathcal {B}_1 \equiv _{\mathrm {LV}} \mathcal {B}_0$ is in the equivalence class $\mathbf {a_0}$ , $\mathcal {A}_1 := \mathcal {B}_1 \setminus \mathcal {B}_0 \equiv _{\mathrm {LV}} \mathcal {B}_1$ is in $\mathbf {a_1}$ , and since $\mathcal {B}_0$ and $\mathcal {B}_1$ are closed under Turing equivalence we also have ${\mathrm {Spec}_{\mathrm {T}} (\mathcal {A}_0)\cap \mathrm {Spec}_{\mathrm {T}} (\mathcal {A}_1)=\emptyset }$ .

To verify (iii), suppose that $\mathbf {deg_{\mathbf {LV}}(}\mathcal {A}\mathbf {)}=\mathbf {a_0\vee a_1}$ for some $\mathcal {A}\in \mathcal {I}$ and let $\mathcal {A}_0^\prime $ and $\mathcal {A}_1^\prime $ satisfy conditions (i) and (ii) above. Then ${\mathbf {deg_{\mathbf {LV}}(}\mathcal {A}\mathbf {)}=\mathbf {deg_{\mathbf {LV}}(}\mathcal {A}_0^\prime \cup \mathcal {A}_1^\prime \mathbf {)}}$ , which implies that $\mathcal {A}\Delta (\mathcal {A}_0^\prime \cup \mathcal {A}_1^\prime )$ is negligible. As $\mathcal {A}_0^\prime $ and $\mathcal {A}_1^\prime $ are disjoint, this implies that $\mathcal {A}_i^\prime \setminus \mathcal {A}$ is negligible for $i=0,1$ . For ${i=0,1}$ , setting ${\mathcal {A}_i= \mathcal {A}_i^\prime \cap \mathcal {A}}$ , we have

$$ \begin{align*} \mathcal{A}_i^\prime= (\mathcal{A}_i^\prime \cap \mathcal{A}) \cup (\mathcal{A}_i^\prime\setminus \mathcal{A}) = \mathcal{A}_i \cup (\mathcal{A}_i^\prime\setminus \mathcal{A}). \end{align*} $$

Thus, $\mathcal {A}_i^\prime $ and $\mathcal {A}_i$ differ only by a negligible set for $i=0,1$ , and thus $\mathcal {A}_0$ and $\mathcal {A}_1$ satisfy (ii). Moreover, since $\mathcal {A}_i\subseteq \mathcal {A}_i^\prime $ for $i=0,1$ , $\mathcal {A}_0$ and $\mathcal {A}_1$ also satisfy (i). Thus, (iii) holds.

To prove Theorem 4.5, we will need to draw upon several classical results from measure theory, as well as several auxiliary lemmata. Here we follow V’yugin’s general proof strategy while filling in more details, especially in isolating and proving Lemma 4.6 below.

As noted in Remark 3.7(iii), for any left-c.e. semi-measure P, $\overline {P}$ is absolutely continuous with respect to $\overline {M}$ . It follows by the Radon–Nikodym Theorem that there is a measurable function $\frac {d\overline {P}}{d\overline {M}}$ such that, for all measurable $\mathcal {X} \subseteq 2^\omega $ ,

$$ \begin{align*} \overline{P}(\mathcal{X})=\int_{\mathcal{X}}{\frac{d\overline{P}}{d\overline{M}}}(X)d\overline{M}(X). \end{align*} $$

The Radon–Nikodym Theorem further guarantees that for any measurable $f\!\colon 2^\omega \rightarrow \mathbb {R}$ such that for all measurable $\mathcal {X} \subseteq 2^\omega $ the property

$$ \begin{align*} \overline{P}(\mathcal{X})=\int_{\mathcal{X}} f(X)d\overline{M}(X) \end{align*} $$

holds, we have $f(X)=\dfrac {d\overline {P}}{d\overline {M}}(X)$ for $\overline {M}$ -almost every $X\in 2^\omega $ .

Proof First, recall that for a measure $\mu $ on $2^\omega $ , a $\mu $ -martingale is a function $d\colon 2^{<\omega }\rightarrow \mathbb {R}^{\geq 0}$ such that

$$ \begin{align*} \mu(\sigma)d(\sigma)=\mu(\sigma0)d(\sigma0)+\mu(\sigma1)d(\sigma1), \end{align*} $$

for every $\sigma \in 2^{<\omega }$ .Footnote ¹

Now, observe that $\dfrac {\overline {P}}{\,\overline {M}\,}$ is an $\overline {M}$ -martingale. Indeed, for every $\sigma \in 2^{<\omega }$ ,

$$ \begin{align*} \overline{M}(\sigma)\dfrac{\overline{P}(\sigma)}{\overline{M}(\sigma)}=\overline{P}(\sigma)=\overline{P}(\sigma0)+\overline{P}(\sigma1)= \overline{M}(\sigma0)\dfrac{\overline{P}(\sigma0)}{\overline{M}(\sigma0)}+\overline{M}(\sigma1)\dfrac{\overline{P}(\sigma1)}{\overline{M}(\sigma1)}. \end{align*} $$

Thus $\lim _{n\rightarrow \infty }\dfrac {\overline {P}(X{\upharpoonright } n)}{\overline {M}(X{\upharpoonright } n)}$ exists for $\overline {M}$ -almost every $X\in 2^\omega $ by the martingale convergence theorem.Footnote ² Thus, by the Radon–Nikodym theorem, we just need to show that

(‡) $$ \begin{align} \overline{P}(\mathcal{A})=\int_{\mathcal{A}} \lim_{n\rightarrow\infty}\dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X), \end{align} $$

for every clopen $\mathcal {A}\subseteq 2^\omega $ (which can then be extended to every measurable $\mathcal {A}\subseteq 2^\omega $ ). Since there is some c such that $\overline {P}(\sigma )\leq c\cdot \overline {M}(\sigma )$ for every $\sigma \in 2^{<\omega }$ , we have for every n that

$$ \begin{align*} \dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)}\leq c, \end{align*} $$

and hence by the dominated convergence theorem,

(†) $$ \begin{align} \lim_{n\rightarrow\infty}\int_{\mathcal{A}} \dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X)= \int_{\mathcal{A}} \lim_{n\rightarrow\infty}\dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X). \end{align} $$

Using ( $\dagger $ ), it now suffices to show that $\overline P(\mathcal {A})$ is equal to the left-hand side of ( $\ddagger $ ). For each sufficiently large N, let $\mathcal {A}=\bigcup _{i=1}^k[\![\sigma _i]\!]$ for distinct ${\sigma _1,\dotsc ,\sigma _k\in 2^N}$ . Then

(1) $$ \begin{align} \lim_{n\rightarrow\infty}\int_{\mathcal{A}} \dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X)&=\int_{\mathcal{A}} \dfrac{\overline{P}(X{\upharpoonright} N)}{\overline{M}(X{\upharpoonright} N)} d\overline{M}(X) \end{align} $$

(2) $$ \begin{align} \phantom{(X)\ \lim_{n\rightarrow\infty}\int_{\mathcal{A}} \dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X)}&=\sum_{i=1}^k\int_{[\![\sigma_i]\!]}\dfrac{\overline{P}(X{\upharpoonright} N)}{\overline{M}(X{\upharpoonright} N)} d\overline{M}(X) \end{align} $$

(3) $$ \begin{align} \phantom{\lim_{n\rightarrow\infty}\int_{\mathcal{A}} \dfrac{\overline{P}(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)} d\overline{M}(X)}&=\sum_{i=1}^k\dfrac{\overline{P}([\![\sigma_i]\!])}{\overline{M}([\![\sigma_i]\!])}\overline{M}([\![\sigma_i]\!])\\[10pt] &=\sum_{i=1}^k\overline{P}([\![\sigma_i]\!])=\overline{P}(\mathcal{A}).\nonumber\\[-46pt]\nonumber \end{align} $$

Lemma 4.7 V’yugin [Reference V’yugin33]

Let P be a left-c.e. semi-measure and suppose that for $\mathcal {B}\subseteq 2^\omega $ , we have $\overline {M}(\mathcal {B}_0)=0$ , where

$$ \begin{align*} \mathcal{B}_0=\bigg\{X\in\mathcal{B}\colon \frac{d\overline{P}}{d\overline{M}}(X)=0\bigg\}. \end{align*} $$

Then $\overline {P}(\mathcal {B})=0$ implies that $\overline {M}(\mathcal {B})=0$ .

Proof By the hypothesis,

$$ \begin{align*} 0=\overline P(\mathcal{B}\setminus\mathcal{B}_0)=\int_{\mathcal{B}\setminus\mathcal{B}_0}\frac{d\overline{P}}{d\overline{M}}(X)d\overline{M}(X). \end{align*} $$

Since $\dfrac {d\overline {P}}{d\overline {M}}(X)\neq 0$ for every $X\in \mathcal {B}\setminus \mathcal {B}_0$ , it follows that $\overline {M}(\mathcal {B}\setminus \mathcal {B}_0)=0$ . Thus, $\overline M(\mathcal {B})=0$ .

Proof Since $\mathcal {B}\subseteq \mathrm {MLR}_\mu $ , by Theorem 3.8, for every $X\in \mathcal {B}$ , there is some c such that

$$ \begin{align*} \mu(X{\upharpoonright} n)\geq c\cdot M(X{\upharpoonright} n), \end{align*} $$

for every n. It follows that for all n,

$$ \begin{align*} \frac{\mu(X{\upharpoonright} n)}{\overline{M}(X{\upharpoonright} n)}\geq\frac{\mu(X{\upharpoonright} n)}{M(X{\upharpoonright} n)}\geq c. \end{align*} $$

By Lemma 4.6, $\dfrac {d\mu }{d\overline M}(X)\neq 0$ for $\overline {M}$ -almost every $X\in \mathcal {B}$ , and so by Lemma 4.7 and the fact that ${\mu (\mathcal {B})=0}$ , it follows that $\mathcal {B}$ is negligible.

Lastly, we need one further classical result. Recall that $\mathcal {A}\subseteq 2^\omega $ is a tailset if for all $\sigma \in 2^{<\omega }$ and all $Y\in 2^\omega $ with $\sigma Y\in \mathcal {A}$ we also have that $\tau Y\in \mathcal {A}$ for every $\tau \in 2^{|\sigma |}$ . That is, for a tailset $\mathcal {A}$ , modifying a finite initial segment of an infinite binary sequence has no bearing on whether that sequence is an element of $\mathcal {A}$ or not. The following result will only be used in the context of Cantor space; for a proof specific to that setting see [Reference Dekker and Myhill9, Theorem 1.2.4].

We can now prove Theorem 4.5.

Proof of Theorem 4.5. Suppose that $\mathbf {r}=\mathbf {a_0}\vee \mathbf {a_1}$ and $\mathbf {a_0}\wedge \mathbf {a_1}=\mathbf {0}$ for some $\mathbf {a_0},\mathbf {a_1}>\mathbf {0}$ . Let ${\mathcal {A}_0,\mathcal {A}_1\in \mathcal {I}}$ be collections of sequences as given by Lemma 4.3 where ${\mathbf {deg_{\mathbf {LV}}(}\mathcal {A}_i\mathbf {)}=\mathbf {a}_i}$ and $\mathcal {A}_i\subseteq (\mathrm {MLR})^{\equiv _{\mathrm {T}} }$ for ${i=0,1}$ . Note that for $i=0,1$ , for each $X\in \mathcal {A}_i$ there is some $Y\in \mathrm {MLR}\cap \mathcal {A}_i$ such that $X\equiv _{\mathrm {T}} Y$ . Let us consider the subcollections of sequences $\mathcal {A}_i^*=\mathrm {MLR}\cap \mathcal {A}_i$ for $i=0,1$ . Since each $\mathcal {A}_i$ is non-negligible, it follows that

$$ \begin{align*} \lambda\bigg(\bigcup_e\Phi^{-1}_e(\mathcal{A}_i)\bigg)>0, \end{align*} $$

for $i=0,1$ . Since each $X\in \mathcal {A}_i$ is Turing equivalent to some $Y\in \mathcal {A}^*_i$ , it follows for $i=0,1$ that

$$ \begin{align*} \bigcup_e\Phi^{-1}_e(\mathcal{A}_i)=\bigcup_e\Phi^{-1}_e(\mathcal{A}^*_i), \end{align*} $$

and hence

$$ \begin{align*} \lambda\bigg(\bigcup_e\Phi^{-1}_e(\mathcal{A}^*_i)\bigg)>0. \end{align*} $$

Then Proposition 3.11 and Lemma 4.8 imply that $\lambda (\mathcal {A}_i^*)>0$ for $i=0,1$ . But each $\mathcal {A}^*_i$ is a measurable tailset, so by Theorem 4.9 it follows that $\lambda (\mathcal {A}^*_i)=1$ for $i=0,1$ , which is impossible as $\mathcal {A}^*_0$ and $\mathcal {A}^*_1$ are disjoint.

4.2 Additional results about the $\mathrm {LV}$ -degrees

It is reasonable to ask whether the degree $\mathbf {r}\vee \mathbf {c}$ is the top degree in $\mathcal {D}_{\mathrm {LV}}$ . V’yugin gave a negative answer to this question by proving that the complement of $\mathbf {r}\vee \mathbf {c}$ in $\mathcal {D}_{\mathrm {LV}}$ is non-negligible. We will give the details of his proof in Section 6, where we will provide the first instance of the technique of building semi-measures that we mentioned in the introduction. However, in this subsection, we provide a simpler proof of this result, and a number of new results about $\mathcal {D}_{\mathrm {LV}}$ .

Given $\mathbf {a}\in \mathcal {D}_{\mathrm {LV}}$ and $\mathcal {A}\subseteq 2^\omega $ such that $\mathbf {deg_{\mathbf {LV}}(}(\mathcal {A})^{\equiv _{\mathrm {T}} }\mathbf {)}=\mathbf {a}$ , we say that $\mathcal {A}$ generates $\mathbf {a}$ or that $\mathbf {a}$ is the $\mathrm {LV}$ -degree generated by $\mathcal {A}$ . We will use the following lemma repeatedly.

Proof (i) First observe that $(\mathcal {A})^{\equiv _{\mathrm {T}} }\setminus (\mathcal {B})^{\equiv _{\mathrm {T}} }\subseteq (\mathcal {A}\setminus \mathcal {B})^{\equiv _{\mathrm {T}} }$ . Indeed, given $X\in (\mathcal {A})^{\equiv _{\mathrm {T}} }\setminus (\mathcal {B})^{\equiv _{\mathrm {T}} }$ , there is some $Y\equiv _{\mathrm {T}} X$ such that $Y\in \mathcal {A}$ and for all $Z\in \mathcal {B}$ , we have $Z\not \equiv _{\mathrm {T}} X$ . It follows that ${Y\notin \mathcal {B}}$ , and hence $X\in (\mathcal {A}\setminus \mathcal {B})^{\equiv _{\mathrm {T}} }$ .

Now suppose that $(\mathcal {A})^{\equiv _{\mathrm {T}} }\setminus (\mathcal {B})^{\equiv _{\mathrm {T}} }$ is non-negligible. By the above observation, $(\mathcal {A}\setminus \mathcal {B})^{\equiv _{\mathrm {T}} }$ is also non-negligible. For $i,j\in \omega $ define

$$ \begin{align*} \mathcal {S}_{i,j}=\{X\in 2^\omega \colon (\exists Y\in \mathcal {A}\setminus \mathcal {B})\; (\Phi _i(Y)=X \;\wedge \;\Phi _j(X)=Y)\}. \end{align*} $$

Then we have

$$ \begin{align*} (\mathcal{A}\setminus\mathcal{B})^{\equiv_{\mathrm{T}} }=\bigcup_{(i,j)\in\omega^2}\mathcal{S}_{i,j}. \end{align*} $$

Since $(\mathcal {A}\setminus \mathcal {B})^{\equiv _{\mathrm {T}} }$ is non-negligible, there is some pair $(i,j)\in \omega ^2$ such that $\mathcal {S}_{i,j}$ is non-negligible. Then by Proposition 3.11, there is some Turing functional $\Psi $ such that $\lambda (\Psi ^{-1}(\mathcal {S}_{i,j}))>0$ . By definition of $\mathcal {S}_{i,j}$ , if ${\Psi (Z)\in \mathcal {S}_{i,j}}$ , then $\Phi _j(\Psi (Z))\in \mathcal {A}\setminus \mathcal {B}$ . Thus $\Psi ^{-1}(\mathcal {S}_{i,j})\subseteq (\Phi _j\circ \Psi )^{-1}(\mathcal {A}\setminus \mathcal {B})$ , and so $\lambda ((\Phi _j\circ \Psi )^{-1}(\mathcal {A}\setminus \mathcal {B}))>0$ . Thus by Proposition 3.11, $\mathcal {A}\setminus \mathcal {B}$ is not negligible.

(ii) If $\mathcal {A}\subseteq \mathcal {B}$ , then $\mathcal {A}\setminus \mathcal {B}=\emptyset $ is trivially negligible. Thus by (i), $(\mathcal {A})^{\equiv _{\mathrm {T}} }\leq _{\mathrm {LV}}(\mathcal {B})^{\equiv _{\mathrm {T}} }$ .

It is natural to ask how the $\mathrm {LV}$ -degree of the Martin-Löf random Turing degrees compares to the $\mathrm {LV}$ -degrees associated with other notions of algorithmic randomness. First we show that the $\mathrm {LV}$ -degree of the Schnorr random Turing degrees is also $\mathbf {r}$ .

Corollary 4.12. Let $\mathrm {R}$ be any notion of algorithmic randomness such that $\mathrm {MLR}\subseteq \mathrm {R}\subseteq \mathrm {SR}$ . Then

$$ \begin{align*}\mathbf{deg_{\mathbf{LV}}(}(\mathrm{R})^{\equiv_{\mathrm{T}} }\mathbf{)}=\mathbf{r}.\end{align*} $$

Proof By Lemma 4.10(ii) and Theorem 4.11, we have

$$ \begin{align*} \mathbf{r}=\mathbf{deg_{\mathbf{LV}}(}(\mathrm{MLR})^{\equiv_{\mathrm{T}} }\mathbf{)}\leq_{\mathrm{LV}} \mathbf{deg_{\mathbf{LV}}(}(\mathrm{R})^{\equiv_{\mathrm{T}} }\mathbf{)}\leq_{\mathrm{LV}}\mathbf{deg_{\mathbf{LV}}(}(\mathrm{SR})^{\equiv_{\mathrm{T}} }\mathbf{)}=\mathbf{r}. \\[-38pt]\end{align*} $$

Thus, notions of randomness such as computable randomness, Kolmogorov–Loveland randomness, and the non-monotonic randomness notions studied in [Reference Bienvenu, Hölzl, Kräling and Merkle2] all are of $\mathrm {LV}$ -degree $\mathbf {r}$ . Similar results hold for notions of randomness stronger than Martin-Löf randomness, as the following result shows.

An immediate consequence of Theorem 4.13 is that for each $n\in \omega $ , the $\mathrm {LV}$ -degree of the collection of n-random sequences is $\mathbf {r}$ . Another consequence is the following, the proof of which is analogous to that of Corollary 4.12.

Corollary 4.14. Let $\mathrm {R}$ be any notion of algorithmic randomness such that $\mathrm {MLR}^{\emptyset '}\subseteq \mathrm {R}\subseteq \mathrm {MLR}$ . Then

$$ \begin{align*}\mathbf{deg_{\mathbf{LV}}(}(\mathrm{R})^{\equiv_{\mathrm{T}} }\mathbf{)}=\mathbf{r}.\end{align*} $$

It follows that notions of randomness such as difference randomness, Demuth randomness, and weak 2-randomness all generate the $\mathrm {LV}$ -degree $\mathbf {r}$ .

We now show that $\mathbf {r}\vee \mathbf {c}$ is not the top $\mathrm {LV}$ -degree by exhibiting an $\mathrm {LV}$ -degree that is incomparable with it. Let $\mathbf {g}$ be the $\mathrm {LV}$ -degree generated by the collection of 1-generic sequences. By Proposition 3.16 this collection is non-negligible.

Let $\mathbf {h}$ be the $\mathrm {LV}$ -degree of the collection of sequences of hyperimmune degree, which is non-negligible by Proposition 3.16.

An additional characterization of $\mathbf {h}$ can be given in terms of the collection $\mathrm {KR}$ of Kurtz random sequences.

Proof ( $\leq _{\mathrm {LV}}$ :) Since every weakly 1-generic sequence is Kurtz random, by Lemma 4.10(ii) we have

$$ \begin{align*}\mathbf{deg_{\mathbf{LV}}(}(\mathrm{W1GEN})^{\equiv_{\mathrm{T}} }\mathbf{)}\leq_{\mathrm{LV}}\mathbf{deg_{\mathbf{LV}}(}(\mathrm{KR})^{\equiv_{\mathrm{T}} }\mathbf{)}.\end{align*} $$

( $\geq _{\mathrm {LV}}$ :). We need to show that the collection of Kurtz random sequences that do not have hyperimmune degree is negligible. As shown by Yu in unpublished work (see [Reference Dekker and Myhill9, Theorem 8.11.12]), every Kurtz random sequence of hyperimmune-free degree is weakly $2$ -random. Since every 2-random sequence has hyperimmune degree, such a sequence must be weakly $2$ -random and not $2$ -random. By Corollary 4.14, the collection of weakly $2$ -random sequences that are not $2$ -random is negligible, from which the conclusion follows.

Since the collection of Kurtz random sequences includes every Martin-Löf random sequence and every 1-generic sequence, we obtain the following result.

$\mathbf {h}<_{\mathrm {LV}}\mathbf {h}\vee \mathbf {c}$ , as the collection of computable sequences is disjoint from the collection of sequences of hyperimmune degree. In fact, $\mathbf {h}\vee \mathbf {c}$ can be identified as the top $\mathrm {LV}$ -degree.

The following corollary, pointed out to the authors by Frank Stephan, allows identifying $\mathbf {h}$ also as the $\mathrm {LV}$ -degree of immunity notions.

Proof Let $\mathrm {COMP}$ denote the computable and $\mathrm {HI}$ denote the hyperimmune sequences. Then

$$ \begin{align*} (2^\omega \setminus \mathrm{COMP})^{\equiv_{\mathrm{T}} }=(\mathrm{IM})^{\equiv_{\mathrm{T}} }\supseteq (\mathrm{BI})^{\equiv_{\mathrm{T}} } \supseteq (\mathrm{BHI})^{\equiv_{\mathrm{T}} } = (\mathrm{HI})^{\equiv_{\mathrm{T}} }. \end{align*} $$

Here the first equality is by Dekker and Myhill [Reference Downey and Hirschfeldt7] (see, for example, [Reference Odifreddi24, item (1) on page 498]), the first inequality is by definition, and the final equality is by Kurtz [Reference Kurtz16, Corollary 2.1]. Using the definition of hyperimmunity given in terms of strong c.e. arrays (see, for example, [Reference Odifreddi24, Definition III.3.7]), it is easy to see that every hyperimmune set is immune, and by applying this to both a set and its complement, we see that every bihyperimmune set is biimmune, giving the second inequality.

Therefore, by Lemma 4.10(ii), we have

$$ \begin{align*} \mathbf{h} =\mathbf{bh}\leq_{\mathrm{LV}} \mathbf{b} \leq_{\mathrm{LV}} \mathbf{i} = \mathbf{c}^c = \mathbf{h}, \end{align*} $$

where the last equality is by Proposition 4.20.

We can also conclude that there is no intermediate $\mathrm {LV}$ -degree between $\mathbf {h}$ and $\mathbf {1}$ .

Let $\mathbf {d}$ denote the LV-degree of the collection of sequences of DNC degree, which is non-negligible by Proposition 3.16. Given that every Martin-Löf random sequence is of DNC degree, we have ${\mathbf {r}\leq _{\mathrm {LV}}\mathbf {d}}$ ; Bienvenu and Patey [Reference Blyth4] showed the strictness of the relation.

Since $\mathbf {c}\wedge \mathbf {d}=\mathbf {0}$ , we have the following corollary.

We can also easily derive the following result and corollary.

Proof Using general properties of Boolean algebras (see, for example, [Reference Bienvenu and Patey5]), we have

$$ \begin{align*}(\mathbf{d}\vee\mathbf{g})\wedge(\mathbf{r}\vee\mathbf{g})^c&=(\mathbf{d}\vee\mathbf{g})\wedge (\mathbf{r}^c\wedge\mathbf{g}^c)=((\mathbf{d}\vee\mathbf{g})\wedge \mathbf{g}^c)\wedge\mathbf{r}^c\\ &=(\mathbf{d}\wedge\mathbf{g}^c)\wedge\mathbf{r}^c=\mathbf{d}\wedge\mathbf{r}^c>_{\mathrm{LV}}\mathbf{0},\end{align*} $$

where the last equality is by Proposition 4.26 and the final inequality is by Theorem 4.24. In particular, $(\mathbf {d}\vee \mathbf {g})>_{\mathrm {LV}} (\mathbf {r}\vee \mathbf {g})$ .

In Section 6, our new application of V’yugin’s technique for building semi-measures implies that the collection of non-computable sequences that are not of DNC degree is non-negligible, which in turn implies that $\mathbf {d}\vee \mathbf {c}$ is not the top $\mathrm {LV}$ -degree. However, we can alternatively derive this latter fact as follows.

The following results about joins in $\mathcal {D}_{\mathrm {LV}}$ are immediate.

The results of this section are summarized in Figure 1.

Figure 1

Standard arrows represent strict separations in the LV-degrees. Dotted arrows represent the following open questions: (a) Is $\mathbf {g}$ a $\mathcal {D}_{\mathrm {LV}}$ -atom? (b) Is $\mathbf {d} \vee \mathbf {g} = \mathbf {h}$ , and thus is $\mathbf {d}\vee \mathbf {g} \vee \mathbf {c} = \mathbf {1}$ ?

4.3 Open questions

We conclude with the following open questions.

Given that $\mathbf {r}$ is a $\mathcal {D}_{\mathrm {LV}}$ -atom, it is also reasonable to ask whether the same holds for $\mathbf {g}$ .

For the definitions of the notions appearing in the following open questions, see a standard reference such as [Reference Dekker and Myhill9].

5.1 The general template

The semi-measure P that we construct will be one induced by a network flow q as described in the previous paragraphs. Here, q will be constructed through an infinite procedure which works in stages. At each stage n, an elementary network $q_n$ together with its extra edge set $\mathcal {X}_n$ will be built. In the end we will then let $q=\lim _n q_n$ and $\mathcal {X}=\bigcup _n \mathcal {X}_n$ . We first make some general informal remarks about the overall procedure, and then go on to describe in formal detail the individual stages.

The general construction template depends upon three parameters:

1. (1) A computable function $\mathfrak {t}\colon \omega \rightarrow \omega $ , called the task function, such that the values

   $$ \begin{align*} \mathfrak{t}(0),\mathfrak{t}(1),\mathfrak{t}(2),\mathfrak{t}(3),\dotsc, \end{align*} $$
   follow the pattern
   $$ \begin{align*} 0,1,0,1,2,0,1,2,3,0,1,2,3,4,\dotsc. \end{align*} $$
   In particular, for each i, the set $\{n\colon \mathfrak {t}(n)=i\}$ is infinite and $\mathfrak {t}(n)\neq \mathfrak {t}(n+1)$ for every n. Every node will be assigned a task; namely, each $\sigma \in 2^{<\omega }$ will be assigned the task $\mathfrak {t}(|\sigma |)$ . For a given task i, the i-nodes are the nodes $\sigma \in 2^{<\omega }$ with $\mathfrak {t}(|\sigma |)=i$ .

2. (2) A computable predicate $B(q',\sigma ,\tau )$ which is defined for elementary networks $q'$ on a $2^{<\omega }$ -digraph G and strings $\sigma $ , $\tau $ such that both are i-nodes for the same $i\in \omega $ .

3. (3) A computable, strictly increasing function $\mathfrak {c}\colon \omega \rightarrow \omega $ .

The predicate B will be determined by the requirements we are attempting to satisfy, while the function $\mathfrak {c}$ will be specifically used to provide the initial values for countdowns to expiration for certain nodes that are active in the construction, in a technical sense to be explained shortly.

We take action towards fulfilling the task i if we add an extra edge connecting two i-nodes; we will refer to such an edge as an i-edge (or as an edge that is assigned to task i). That is, an edge $(\sigma ,\tau )\in \mathcal {E}_G$ is an i-edge if $\mathfrak {t}(|\sigma |)=\mathfrak {t}(|\tau |)=i$ . Let $\mathcal {X}[i]$ be the set of extra edges assigned to task i. Note that we never assign normal edges to any task i, since $\mathfrak {t}(n)\neq \mathfrak {t}(n+1)$ for every n.

In the course of the construction, for $j<i$ , we would ideally want to first perform all actions necessary for task j before beginning to work on task i. That is, for every extra edge $(\sigma ,\tau )$ between a pair of i-nodes $\sigma $ and $\tau $ and for any extra edge $(\sigma ',\tau ')$ assigned to some task j with $j<i$ , we would like to have $|\tau '|<|\sigma |$ . But, in fact, during the construction we will not be able to always ensure this property. After having added $(\sigma ,\tau )$ for task $\mathfrak {t}(|\sigma |)=\mathfrak {t}(|\tau |)=i$ it may turn out later in the construction that further edges for task j need to be added. Adding them will then invalidate our previous actions for task i. The edge $(\sigma ,\tau )$ stays in the digraph, but we will consider it a failure, as it does not help us achieve the desired goal for task i. While the presence of $(\sigma ,\tau )$ also causes no harm, we will, at some later stage, have to completely restart the construction for task i. The construction can therefore be thought of as a type of finite injury argument.

For a given task i, we will need to talk about the minimal length of an i-node to which an extra edge can be attached. We thus define the following auxiliary function w: Let $q'$ be an elementary network on G, with the associated set of extra edges $\mathcal {X}'$ through which some of the flow passes. Then for each $i\in \omega $ , we define

$$ \begin{align*} w(i,q')=\min\{n\colon\mathfrak{t}(n)=i \;\wedge\; (\forall j<i)(\forall(\sigma,\tau)\in \mathcal{X}'[j])\; |\tau|<n\}. \end{align*} $$

That is, $w(i,q')$ is the least n such that (i) $\mathfrak {t}(n)=i$ and (ii) every edge in G assigned to task j for some $j<i$ ends in a node of length less than n.

For an arbitrary (that is, not necessarily elementary) computable network $q'$ , $w(i,q')$ may be undefined in general. But in fact, for q’s built using the template described here, $w(i,q')$ will always be well-defined by the above equation, and $w(i,q)=\lim _n w(i,q_n)$ , where $q_n$ is the level n elementary restriction of q. The lengths n where $w(i,q_{n-1})\neq w(i,q_n)$ correspond to the failures described above.

Another component of our construction is that at each stage, a number of nodes may be set as active, serving as candidates to which an extra edge may be attached. Before activation, all flow into a node $\sigma $ will be equally divided to flow into $\sigma $ ’s direct successor nodes $\sigma 0$ and $\sigma 1$ through the corresponding normal edges. To activate a node we reduce the flow from $\sigma $ into $\sigma 0$ and $\sigma 1$ , resulting in a certain amount of flow into $\sigma $ being temporarily unused. We say that we have delayed part of the flow. In a later step we may then attach an extra edge to $\sigma $ and direct the delayed, leftover flow through this new edge.

More formally, for an elementary network $q'$ , we have a function $d'$ , called a flow-delay function, which satisfies

$$ \begin{align*} d'(\sigma)=1-q'(\sigma,\sigma 0)-q'(\sigma,\sigma1), \end{align*} $$

for every $\sigma \in 2^{<\omega }$ . This is precisely the proportion of flow into $\sigma $ that is prevented from flowing into $\sigma 0$ and $\sigma 1$ . The active nodes consist of those nodes $\sigma $ such that $0<d'(\sigma )<1$ ; the construction will be such that if we block all of the flow through a node $\sigma $ by setting $d'(\sigma )=1$ , then it, and all of its extensions, will never be activated from that point on. Moreover, for $j<i$ , to enforce the requirement that all j-edges end before any i-edges begin, whenever we attach an extra edge to a j-node $\tau $ , all active i-nodes whose length is less than $|\tau |$ become unusable as, by the conditions in the construction, we will never attach edges to such nodes. We will call such nodes deactivated. Intuitively, we can then think of the flow that was delayed at such nodes as wasted.

Next, given a node $\sigma $ to which we would like to attach an extra edge, there is a function $\beta (\sigma ,q',n)$ that selects (somewhat arbitrarily) a candidate $\tau \succ \sigma $ of length n for connecting an edge between $\sigma $ and $\tau $ in an elementary network $q'$ in such a way as to satisfy the predicate B, if such a $\tau $ exists. Specifically,

$$ \begin{align*} \beta(\sigma,q',n)=\min\{\tau\in2^n \colon \tau \succ \sigma \;\wedge\; \mathfrak{t}(|\sigma|)=\mathfrak{t}(|\tau|) \;\wedge\; B(q',\sigma,\tau)\}, \end{align*} $$

where the minimum refers to the lexicographic ordering of strings $\tau $ of length n.

After these informal remarks, we describe in detail how to construct the network q, with its set of extra edges $\mathcal {X}$ and its flow-delay function d: As mentioned at the start of this subsection, we first build a sequence $(q_n,\mathcal {X}_n,d_n)_{n\in \omega }$ , where each $q_n$ is an elementary network with associated set of extra edges $\mathcal {X}_n$ . For each $n\in \omega $ we will let $d_n$ denote the flow-delay function associated with $q_n$ . In the end we will set $q= \lim _nq_n$ , $\mathcal {X}=\bigcup _n \mathcal {X}_n$ , and $d=\lim _n d_n$ .

The definition of the sequence $(q_n, \mathcal {X}_n, d_n)_{n\in \omega }$ proceeds in stages as follows: For $n=0$ ,

$$ \begin{align*} q_0(\sigma,\tau)=\begin{cases} 1/2 & \text{if}\ \tau=\sigma0\ \text{or}\ \tau=\sigma1,\\ 0 & \text{otherwise}. \end{cases} \end{align*} $$

Clearly $d_0(\sigma )=0$ for all $\sigma \in 2^{<\omega }$ and $\mathcal {X}_0=\emptyset $ .

Suppose we have defined $(q_{n-1},\mathcal {X}_{n-1},d_{n-1})$ , where for all $(\sigma ,\tau )\in \mathcal {X}_{n-1}$ , $|\tau |<n$ . We will first define $\mathcal {X}_n, d_n$ , and then $q_n$ . The goal of this stage of the construction is to attach an extra edge connecting a $\mathfrak {t}(n)$ -node whose length is strictly less than $n-1$ with a $\mathfrak {t}(n)$ -node of length n. We consider two cases.

Case 1: $w(\mathfrak {t}(n),q_{n-1})=n$ . This means that the extra edges in $\mathcal {X}_{n-1}$ assigned to some task $j<\mathfrak {t}(n)$ terminate in nodes of length $\leq n-1$ , and this is the least n for which this holds. This further implies that there is no active $\mathfrak {t}(n)$ -node of length less than n to which we can attach an extra edge. We thus take the following steps:

1. (i) Set $\mathcal {X}_n=\mathcal {X}_{n-1}$ .

2. (ii) Set $d_n(\sigma )= \begin {cases} 1/\mathfrak {c}(n) & \text {if}\ |\sigma |=n,\\ d_{n-1}(\sigma ) & \text {otherwise.}\end {cases}$

Setting $d_n(\sigma )=1/\mathfrak {c}(n)$ for each $\sigma $ of length n has the effect of activating these nodes, in anticipation of attaching a $\mathfrak {t}(n)$ -edge to them later in the construction. We call this the initial activation of the nodes, since Case 1 is the case where we begin working towards task i (or where we begin anew to work towards it, in case that a previous injury has occurred for task i that requires us to start over).

Recall that $\mathfrak {c}$ provides the initial value for a countdown mechanism that we will use during the construction; once we implement this template for a specific application, we will have to choose $\mathfrak {c}$ carefully to ensure that a positive amount of flow stays in the network in the limit.

Case 2: $w(\mathfrak {t}(n),q_{n-1})<n$ . Our hope in this case is that we can attach some extra edges from $\mathfrak {t}(n)$ -nodes of length $\geq w(\mathfrak {t}(n), q_{n-1})$ to $\mathfrak {t}(n)$ -nodes of length n. Thus we search for $\sigma \in 2^{<\omega }$ such that the following four conditions hold:

1. (a) $w(\mathfrak {t}(n),q_{n-1})\leq |\sigma |<n$ ;

2. (b) $0<d_{n-1}(\sigma )<1$ ;

3. (c) $\beta (\sigma ,q_{n-1},n)$ is defined; and

4. (d) $\sigma \prec \rho $ implies that $(\sigma ,\rho )\notin \mathcal {X}_{n-1}$ .

Condition $(a)$ guarantees that the start of the new edge occurs beyond the end of any currently present j-edge for $j<\mathfrak {t}(n)$ ; in particular, this rules out attaching edges at deactivated nodes. Condition $(b)$ guarantees that $\sigma $ is active (henceforth, we will refer to a node $\sigma $ such that $0<d_n(\sigma )<1$ as active at stage n). Condition $(c)$ guarantees that $\sigma $ is assigned to task $\mathfrak {t}(n)$ and that there is a length n node that can serve as the endpoint of a new $\mathfrak {t}(n)$ -edge we want to attach at $\sigma $ (that is, the predicate B is satisfied). Finally, condition $(d)$ guarantees that no extra edge has been previously attached starting at  $\sigma $ .

Let $\mathcal {C}_n$ be the set of $\sigma \in 2^{<\omega }$ such that conditions $(a)$ – $(d)$ are satisfied. Then we have two subcases to consider.

Subcase 2.1: $\mathcal {C}_n\neq \emptyset $ . For every $\sigma \in \mathcal {C}_n$ and every $\tau \succ \sigma $ with $|\tau |=n$ we let

$$ \begin{align*} d_n(\tau)= \left\{ \begin{array}{lll} 0 & \mbox{if } \tau=\beta(\sigma,q_{n-1},n), \\ d_{n-1}(\sigma)/(1-d_{n-1}(\sigma)) & \mbox{else}. \end{array} \right. \end{align*} $$

For all other $\tau $ we let $d_n(\tau ) = d_{n-1}(\tau )$ .

By condition $(b)$ above, setting $d_n(\tau )=0$ makes $\tau $ inactive, meaning that we will not add any further $\mathfrak {t}(n)$ -edges to any extensions of $\tau $ , with one possible exception: It may be that at a later stage $n'>n$ with $\mathfrak {t}(n') < \mathfrak {t}(n)$ , a new $\mathfrak {t}(n')$ -edge is added, which at some even later stage $n''>n'>n$ with $\mathfrak {t}(n'') = \mathfrak {t}(n)$ would lead to Case 1 above occurring again for task ${\mathfrak {t}(n'') = \mathfrak {t}(n)}$ . This would in turn lead to all strings of length $n''$ getting initially activated for task $\mathfrak {t}(n'') = \mathfrak {t}(n)$ at stage $n''$ where we begin anew to work on that task. In this case we say that task $\mathfrak {t}(n'') = \mathfrak {t}(n)$ has been injured by task $\mathfrak {t}(n')$ .

When a node is assigned a non-zero delay value by the second line above, we call this its non-initial activation. This is because that new delay value at node $\tau $ is a consequence of an earlier assignment of a non-zero delay value to the strictly shorter node $\sigma $ .

Note that when initially activating a node $\sigma $ , we assign a delay of the form $1/k$ , where $\mathfrak {c}(|\sigma |)=k$ for some $k\in \omega $ . Moreover, the mapping ${d\mapsto d/(1-d)}$ used for non-initial activations maps such a number to $1/(k-1)$ , which is then mapped to $1/(k-2)$ , and so on. Note further that the nodes where these new delay values are set are by construction $\mathfrak {t}(n)$ -nodes. The reciprocal of these assigned delay values are positive integers, and we can interpret them as a counter counting down by $1$ along a path every time a $\mathfrak {t}(n)$ -edge branches off it; see Figure 2.

Figure 2

An edge for task $\mathfrak {t}(n)$ is added. The root of the edge was initially activated with counter value $\mathfrak {c}(n)$ . The node at the end of the new edge has delay value $0$ , thus is inactive. All other extensions of the root receive a positive delay value by non-initial activation, and thereby become active. The counter value on these nodes, which is the reciprocal of the value of d on the respective node, has been reduced by $1$ compared to the counter value on the root. Note how other, completely independent $\mathfrak {t}(n)$ -edges can occur off to the side.

Even on the same path different tasks are initially activated separately at different nodes of appropriate length. The countdown happens separately for all tasks, as a new delay value assigned to an i-node depends on the delay value of an i-node of shorter length, and not on the delay values of j-nodes with $i\neq j$ . It therefore makes sense to talk about the i-counter for task i along a given path, and we will use this expression in the informal explanations in the sequel.

As we continue to add edges for task $\mathfrak {t}(n)$ that branch off a path, the $\mathfrak {t}(n)$ -counter may eventually reach $1$ on some initial segment of that path. Such a node is then by definition inactive. (Formally, the counter reaching $1$ means that the delay value along the path has increased until all flow is blocked at a value of $1$ .) Once this happens, by construction, we stop attaching $\mathfrak {t}(n)$ -edges on any extension of that initial segment of the path.

Next, we set

$$ \begin{align*} \mathcal{X}_n=\mathcal{X}_{n-1}\cup\{(\sigma,\beta(\sigma,q_{n-1},n))\colon\sigma\in \mathcal{C}_n\}, \end{align*} $$

and

$$ \begin{align*} q_n(\sigma,\tau)= \left\{ \begin{array}{lll} \frac{1}{2}(1-d_n(\sigma)) & \mbox{if } \tau=\sigma0\;\text{or}\;\tau=\sigma1,\\ d_{n}(\sigma) & \mbox{if } (\sigma,\tau)\in \mathcal{X}_n,\\ 0 & \mbox{otherwise.} \end{array} \right. \end{align*} $$

Note that for $j>\mathfrak {t}(n)$ , $w(j,q_k)>n$ for all $k \geq n$ . In particular, we are now prevented from attaching an edge to any j-nodes that were active at the beginning of this stage; as mentioned above we call such nodes deactivated.

Subcase 2.2: $\mathcal {C}_n=\emptyset $ . Then we set $d_n=d_{n-1}$ , $\mathcal {X}_n=\mathcal {X}_{n-1}$ , and $q_n=q_{n-1}$ . No new nodes are activated, nor do any active nodes become deactivated.

To finalize the outline of the construction template we lastly set ${q=\lim _n q_n}$ , $d=\lim _n d_n$ , and $\mathcal {X}=\bigcup _n \mathcal {X}_n$ . It is not difficult to check that q and d are computable functions and that $\mathcal {X}$ is a computable set. It then follows from Lemma 5.5 that the resulting q-flow P, as in Definition 5.4, is a left-c.e. semi-measure.

5.2 Verification of the general template

We now work to establish the desired properties of the constructed objects q, d, $\mathcal {X}$ , R, P, and so on. For the sake of notational simplicity, during this verification, we will again use the letters $q_n$ , $d_n$ , and $\mathcal {X}_n$ , for $n\in \omega $ , to refer to the finite approximations of q, d, and $\mathcal {X}$ that we built in the previous subsection. In particular note that, for q, these finite approximations $q_n$ , $n\in \omega $ , coincide with the sequence of elementary restrictions discussed on page 23.

Before we implement this template, we show that a number of features of the construction can be established independently of the concrete implementation. First, the following two lemmata show that the construction prevents certain relative arrangements of extra edges.

Proof The fact that $(\zeta ,\xi )$ is added implies that $\zeta $ was activated at stage $|\zeta |$ and cannot have been deactivated until after stage $|\xi |$ . This implies in particular that between stages $|\zeta |$ and $|\xi |$ no injury of task $\mathfrak {t}(\zeta )$ occurred, so that $\sigma $ cannot have been initially activated at stage $|\sigma |$ . Assume that $\sigma $ was activated non-initially. Then there must exist a sequence of extra $\mathfrak {t}(\zeta )$ -edges

$$ \begin{align*}(\nu_1, \mu_1), (\nu_2,\mu_2), (\nu_3,\mu_3), \dots, (\nu_\ell, \mu_\ell)\end{align*} $$

such that for all $2 \leq i \leq \ell $ we have

$$ \begin{align*}\zeta=\nu_1, \ \ \ \nu_{i-1} \prec \nu_i,\ \ \ |\mu_{i-1}|=|\nu_i|,\ \ \ \mu_{i-1}\neq\nu_i,\ \ \ |\mu_\ell| = |\sigma|, \ \ \ \text{and} \ \ \ \mu_\ell \neq \sigma;\end{align*} $$

see Figures 2 and 3. But, by condition (d) in Case 2 of the construction, the presence of the edge $(\zeta , \mu _1)$ would have precluded $(\zeta ,\xi )$ from having been added later, a contradiction.

Figure 3

A sequence of extra edges branching off a given path A. Note how the length of the start point of every edge has to coincide with the length of the endpoint of the previous edge branching off the path.

Note that without the condition “ $|\xi |\leq |\tau |$ ” the statement is false, as typically there are many pairs of extra edges for which that condition does not hold but which satisfy the other conditions in the statement.

Next, we establish that the work towards every individual task terminates eventually.

Proof First, observe that if $\mathcal {X}[j]$ is finite for every $j<i$ , then ${w(i,q)<\infty }$ . It is therefore sufficient to prove the first part of the statement.

So suppose that i is minimal such that $\mathcal {X}[i]$ is infinite. Then by the previous observation we have $w(i,q)<\infty $ . For $\sigma $ with $|\sigma |\geq w(i,q)$ , define $m_\sigma $ to be the maximal $m>w(i,q)$ such that there is an edge ${(\sigma {\upharpoonright } m,\tau ) \in \mathcal {X}[i]}$ where $\tau $ is incomparable with $\sigma $ . If no such m exists, set ${m_\sigma = w(i,q)}$ .

Then define a function u via

$$ \begin{align*} u(\sigma)=\begin{cases} 1/d(\sigma{\upharpoonright} m_\sigma) & \text{if } d(\sigma{\upharpoonright} m_\sigma)>0, |\sigma|\geq w(i,q), \\ \mathfrak{c}(w(i,q)) & \text{if } |\sigma| < w(i,q).\\ \end{cases} \end{align*} $$

Note that these two cases are exhaustive; to see this assume that $|\sigma |\geq w(i,q)$ . If $m_\sigma =w(i,q)$ , then by construction $d(\sigma {\upharpoonright } m_\sigma ) = 1/\mathfrak {c}(m_\sigma )>0$ . The only other possibility is that $m_\sigma $ is the maximal $m>w(i,q)$ such that there is an edge ${(\sigma {\upharpoonright } m,\tau ) \in \mathcal {X}[i]}$ where $\tau $ is incomparable with $\sigma $ . But then $d(\sigma {\upharpoonright } m_\sigma )> 0$ as well, as otherwise the edge $(\sigma {\upharpoonright } m_\sigma ,\tau )$ would not have been added according to the conditions in the construction.

We claim that $u(\sigma )$ is an upper bound on the number of possible i-edges branching off below length $\max (w(i,q),|\sigma |)$ from any path going through  $\sigma $ .

First, consider $\sigma $ meeting the conditions of the first line of the definition, and such that an edge $(\sigma {\upharpoonright } m_\sigma ,\tau )$ as in the definition of $m_\sigma $ exists. Since by the choice of $m_\sigma $ the edge $(\sigma {\upharpoonright } m_\sigma ,\tau )$ is the last edge branching off above $\sigma $ , and by the discussion of the i-counter mechanism above, we know that then at most $\frac {1}{d(\sigma {\upharpoonright } m_\sigma )}-2$ further i-edges can branch off below $\sigma $ from any path extending $\sigma $ , and the claim in this case follows.

Secondly, consider $\sigma $ meeting the conditions of the first line of the definition, but where an edge of the form $(\sigma {\upharpoonright } m_\sigma ,\tau )$ as in the definition of $m_\sigma $ does not exist. For those $\sigma $ we have that a parent $\rho $ of $\sigma $ with $|\rho |=w(i,q)$ has been initially activated, but that there is no extra i-edge that branches off between $\rho $ and $\sigma $ . Again by the discussion of the i-counter mechanism, we know that then at most $\mathfrak {c}(w(i,q)) - 1$ many $i$ -edges can branch off below $\sigma $ from any path extending $\sigma $ . Since

$$ \begin{align*}u(\sigma)=1/d(\sigma{\upharpoonright} m_\sigma)=1/d(\sigma{\upharpoonright} w(i,q))=\mathfrak{c}(w(i,q)),\end{align*} $$

the claim in this case follows.

Lastly, consider $\sigma $ satisfying $|\sigma |<w(i,q)$ . Let $\tau \succ \sigma $ be of length $w(i,q)$ . Then $\tau $ is initially activated with $d(\tau )=1/\mathfrak {c}(|\tau |)$ . By the definition of u, $u(\sigma )=u(\tau )$ , and we can argue as in the previous paragraph to conclude that at most $\mathfrak {c}(w(i,q)) - 1 \textrm{ many } i$ -edges can branch off below length $w(i,q)$ from any path extending $\sigma $ .

It should now be clear that u is constant on all strings $\sigma $ with $|\sigma | \leq w(i,q)$ ; and that for arbitrary strings $\sigma $ and $\tau $ with $\sigma \preceq \tau $ we have $u(\sigma ) \geq u(\tau )$ . We then define the function ${\widehat u\colon 2^\omega \rightarrow \omega }$ by letting, for every $A \in 2^\omega $ ,

$$ \begin{align*} \widehat u(A) = \min\{n\colon u(A {\upharpoonright} n)= u(A {\upharpoonright} \ell) \text{ for all } \ell \geq n\}. \end{align*} $$

We claim that the function $\widehat u$ is continuous. This is because $(a)\, u$ is non-increasing over longer and longer initial segments of a path A, $(b)\, u$ only takes integer, positive values, and $(c)$ a decrease in u cannot happen arbitrarily late along A. This last point $(c)$ follows from the two facts that $($ i $)$ at every node at most one edge starts (by construction) and that $($ ii $)$ for an i-edge branching off A at $A{\upharpoonright } \ell $ we must have that $\ell $ is either $w(i,q)$ or the length of the endpoint of the previous i-edge branching off A; otherwise $A{\upharpoonright } \ell $ would not be active; see Figure 3. Therefore, for a long enough initial segment $A {\upharpoonright } k$ of A, $u(A {\upharpoonright } k)$ has stabilized, meaning that $A {\upharpoonright } k$ already determines $\widehat u(A)$ .

Because $2^\omega $ is compact, $\widehat u$ is bounded by some $N \in \omega $ , meaning in particular that ${u(\sigma )=u(\sigma {\upharpoonright } N)}$ for all $\sigma $ with $|\sigma |\geq N$ . But then no new i-edge $(\sigma ,\tau )$ can be attached to any such $\sigma $ , as that would imply $u(\tau ) < u(\sigma )$ , contradicting the choice of N. Thus $\mathcal {X}[i]$ cannot be infinite.

Note that a sequence $X\in 2^\omega $ becomes i-discarded if there exists an initial segment $X {\upharpoonright } k$ such that the counter for task i has reached the final value $1$ on $X {\upharpoonright } k$ . By the conditions stated in Case 2 of the construction, below such an $X {\upharpoonright } k$ no further extra edges for task i will branch off of X, hence the name “discarded.”