††thanks: This research was partially supported by Russian foundation for
fundamental research: 20-01-00203-a.

# Degrees of randomized computability: decomposition into atoms

Vladimir V. V’yugin  Institute for Information Transmission Problems, Russian
Academy of Sciences, Bol’shoi Karetnyi per. 19, Moscow GSP-4, 127994, Russia.
e-mail<EMAIL_ADDRESS>
###### Abstract

In this paper we study the structural properties of LV-degrees of the algebra
of collections of sequences that are non-negligible in the sense that they can
be computed by a probabilistic algorithm with positive probability. We
construct atoms and infinitely divisible elements of this algebra generated by
sequences, which cannot be Martin-Löf random and, moreover, these sequences
cannot be Turing equivalent to random sequences. The constructions are based
on the corresponding templates which can be used for defining the special LV-
degrees. In particular, we present the template for defining atoms of the
algebra of LV-degrees and obtain the decomposition of the maximal LV-degree
into a countable sequence of atoms and their non-zero complement – infinitely
divisible LV-degree. We apply the templates to establish new facts about
specific LV-degrees, such as the LV-degree of the collection of sequences of
hyperimmune degree. We construct atoms defined by collections of hyperimmune
sequences, moreover, a representation of LV-degree of the collection of all
hyperimmune sequences will be obtained in the form of a union of an infinite
sequence of atoms and an infinitely divisible element.

###### keywords:

Algorithmic information theory , Degrees of randomizing computability , Turing
degrees , Randomized Turing machine , Recursive functions , A priory
semimeasure , Martin-Löf random sequences

##  1 Introduction

The problem of the existence of nonstochastic objects has been discussed in
seventies at Kolmogorov’s seminar in the Moscow State University (see also
Cover et al. [2]). Following Levin [8], Levin and V’yugin [7], V’yugin [21,
22, 24]), the most suitable objects for such a study are infinite binary
sequences and the problem should be considered in the information aspect, that
is, the problem is whether we can generate “nonstochastic information” using a
probabilistic Turing machine and what types of nonstochastic information can
be generated using probabilistic these machines.

We will study the properties (collections or Borel sets) of infinite binary
sequences, as carriers of certain information, i.e. such properties should be
invariant with respect to the encoding methods. We will consider the encoding
methods of the most general type – algorithmic operators.

The algebra of collections (of infinite sequences) that are closed under
Turing equivalence were introduced by Levin and V’yugin [7] and studied by
V’yugin [22]. Roughly speaking, given two such collections $A$ and $B$,
$A\preceq B$ in this ordering if $A\setminus B$ is negligible, i.e. the
Levin’s a priory (semi)measure of this set is equal to zero. This is
equivalent to the fact that no probabilistic Turing machine can produce a
sequence from this set with a positive probability. See about the a priory
semimeasure in Zvonkin and Levin [26], Levin and V’yugin [7], and in
Solomonoff [18, 19].

We call any two invariant collections $A$ and $B$ equivalent, $A\sim B$, if
$A\preceq B$ and $B\preceq A$, i.e., these sets differ on a negligible set. We
consider the factor algebra with respect to this equivalence, its element is
defined as $[A]=\\{B:B\sim A\\}$.

The degree structure associated with this ordering is a Boolean algebra which
was called by V’yugin [22] the algebra of invariant properties. This algebra
was recently called by Bienvenu and Patey [1] and in Holzl and Porter [4] the
algebra of Levin-V’yugin degrees (or LV-degrees). The idea of studying this
algebra was put forward by Leonid Levin.

In this paper we study structural properties of LV-degrees of collections of
sequences that are non-negligible in the sense that they can be computed by a
probabilistic algorithm with positive probability. The equivalence class of
all negligible collections defines the zero element while all infinite
sequences defines the maximal – unit element, of this algebra.

Two natural elements of this algebra can be distinguished. This is the element
generated by non-computable Martin-Löf random sequences and the element
generated by computable sequences.

It was proved by V’yugin [21, 22] that the complement of these two elements is
non-zero. Using the probabilistic Turing machines, we can generate infinite
sequences which are non-random with respect to any computable measure and,
moreover, they cannot be Turing equivalent to random sequences. We say that
such sequences carry non-random information.

In this work, we will study the properties of of LV-algebra. Levin and V’yugin
[7] pointed out that all non-computable Martin-Löf sequences define the atom
of LV-algebra in the sense that such an element cannot be represented as a
union of two incomparable non-zero elements. Computable sequences form the
atom in a trivial way.

In this paper we construct infinitely many other atoms defined by collections
of non-random sequences. We will also show that the complement of all atoms of
the LV-algebra is nontrivial. The complement of all atoms is an infinitely
divisible element. Thus, we get a representation of the unit element of LV-
degrees in the form of a union of an infinite sequence of atoms, two of which
have the natural interpretation, and an infinitely divisible element. The
constructions are based on the corresponding templates. In particular, we
present the template for defining atoms of the algebra of LV-degrees.

Also, we correct and improve the construction of the atoms from V’yugin [22],
which is insufficient to achieve the desired result. The author is grateful to
Rupert Holzl and Cristopher Porter who noticed this insufficiency.

An excellent analysis of the relationship between LV-degrees and Turing
degrees is given in the review by Holzl and Porter [4], where the idea of the
construction from V’yugin [22] is also explained.

We will point out the connection between the properties of LV-algebra and
classical properties from computability theory. In particular, we apply
results on the interactions between notions of randomness and Turing
reducibility to establish new facts about specific LV-degrees, such as the LV-
degrees of the collections of hyperimmune sequences which are characteristic
sequences of hyperimmune sets. We will construct atoms and infinitely
divisible element defined by collections of hyperimmune sequences. Thus, a
representation of LV-degree of the collection of all hyperimmune sequences
will be obtained in the form of a union of an infinite sequence of atoms and
an infinitely divisible element.

##  2 Preliminaries

Let $\Xi$ be the set of all finite binary sequences, $\Omega$ be the set of
all infinite binary sequences, $\lambda$ be the empty sequence. In what
follows by a sequence (finite or infinite) we mean the binary sequence, i.e.,
the sequence $\omega_{1}\omega_{2}\dots$, where $\omega_{i}\in\\{0,1\\}$ for
$i=1,2,\dots$. For any finite or infinite
$\omega=\omega_{1}\dots\omega_{n}\dots$, we denote its prefix (initial
fragment) of length $n$ as $\omega^{n}=\omega_{1}\dots\omega_{n}$. We write
$x\subseteq y$ if a sequence $y$ is an extension of a sequence $x$, $l(x)$ is
the length of $x$.

Let $\cal R$ be the set of all real numbers extended by adding the infinities
$-\infty$ and $+\infty$, $\cal N$ and $\cal Q$ – be the sets of all positive
integer numbers and of all rational numbers. Let $[r]$ denotes the integer
part of a real number $r$.

We assume that the reader is familiar with the basics of computability and
algorithmic randomness theory (for instance, the material covered in Rogers
[12], Soare [17], Nies [11], Downey and Hirschfeldt [3], Gács [5],
Vereshchagin et al. [15], and Li and Vitanyi [9]).

We need a one-to-one enumeration of all ordered pairs of positive integers. We
fix some form of this enumeration. We use the natural correspondence between
finite binary sequences and nonnegative integers: $\lambda$–$0$, $0$–$1$,
$1$–$2$, $00$–$3$, $01$–$4$, $11$–$5$, $000$–$6,\dots$. We will identify any
ordered pair of positive integer numbers $\langle i,j\rangle$ and its ordinal
number. A one-to-one enumeration of all ordered triples $\langle i,j,k\rangle$
also can be defined in a similar way: $\langle i,j,k\rangle=\langle\langle
i,j\rangle,k\rangle$. We denote the inverse functions $[\langle
i,j\rangle]_{1}=i$ and $[\langle i,j\rangle]_{2}=j$. Also, $[\langle
i,j,k\rangle]_{1}=i$, $[\langle i,j,k\rangle]_{2}=j$ and $[\langle
i,j,k\rangle]_{3}=k$.

We fix a model of computation. Algorithms may be regarded as Turing machines
and so the notion of a program and a time of computation will be well-defined.
Our considerations will be invariant under polynomial computation time, so the
results will be machine-independent. An algorithm transforms finite objects
into finite objects. Integer and rational numbers (but no reals) are examples
of finite objects. Finite sequences of finite objects are again finite
objects. The main property of finite objects that we use is that they can be
enumerated with positive integers, and therefore they can be arguments of
computable (partial recursive) functions and algorithms.

A function $f$ is called partial recursive if there is an algorithm (Turing
machine) computing values of $f$. For any input $x$ the corresponding Turing
machine when fed with $x$ stops after several steps and outputs the result
$f(x)$ if $f(x)$ is defined and never stops otherwise. We call a function $f$
total if $f(x)$ is defined for every $x$.

Define

$f^{n}(x)=\left\\{\begin{array}[]{l}f(x)\mbox{ if }f(x)\mbox{ is computed in
}n\mbox{ steps}\\\ \infty\mbox{, otherwise},\end{array}\right.$

where $f$ is a partial recursive function and $n$ is a positive integer
number.

We will use the recursive sequence $\phi_{i}$ of all partial recursive
functions. This means that there is partial recursive universal function
$U(i,x)=\phi(x)$ such that for any partial recursive function $f$ there exists
an $i$ such that $\phi_{i}(x)=U(i,x)=f(x)$ for each $x$, where both sides if
this equality are defined or undefined simultaneously.

A set of finite objects is called recursively enumerable if it is a domain of
some computable function. A nonempty set $A$ is recursively enumerable if and
only if it is the range of some total recursive (computable) function. A set
$A$ of finite objects is called (algorithmically) decidable (recursive) if $A$
and the complement of $A$ are recursively enumerable.

Let $A$ be a set of all finite objects of certain type. A function $f\colon
A\rightarrow\cal R$ is called lower semicomputable if $\\{(r,x):x\in\Xi,\
r\in{\cal Q},r<f(x)\\}$ is a recursively enumerable set. This means that there
is an algorithm which when fed with a rational number $r$ and a finite object
$x$ eventually stops if $r<f(x)$ and never stops otherwise. In other words,
the semicomputability of $f$ means that if $f(x)>r$ this fact will sooner or
later be learned, whereas if $f(x)\leq r$ we may be for ever uncertain.

We use also a concept of computable operator (operation) on $\Xi\bigcup\Omega$
(Zvonkin and Levin [26], Uspenskyi et al. [25]). Let $\hat{F}$ be a
recursively enumerable set of ordered pairs of finite sequences (graph of a
computable operator) satisfying the following properties:

  * •

$(x,\lambda)\in\hat{F}$ for any $x$, where $\lambda$ is the empty sequence;

  * •

if $(x,y)\in\hat{F}$, $x\subseteq x^{\prime}$ and $y^{\prime}\subseteq y$ then
$(x^{\prime},y^{\prime})\in\hat{F}$;

  * •

if $(x,y)\in\hat{F}$ and $(x,y^{\prime})\in\hat{F}$ then $y\subseteq
y^{\prime}$ or $y^{\prime}\subseteq y$.

A computable operator $F$ is defined using the graph $\hat{F}$ as follows

$F(\omega)=\sup\\{y:\exists x(x\subseteq\omega\&(x,y)\in\hat{F}\\},$

where $\omega\in\Omega\bigcup\Xi$ and $\sup$ is under partial ordering
$\subseteq$ on $\Xi$.

Informally, the computable operator $F$ is defined by some algorithm which
when fed with an infinite or a finite sequence $\omega$ takes it sequentially
bit by bit, processes it and produces an output sequence also sequentially bit
by bit.

In what follows we will use the modified version of computable operator, where

$\displaystyle\tilde{F}(x)=\sup\\{y:l(y)\leq l(x)\&\exists
x^{\prime}(x^{\prime}\subseteq x\&(x^{\prime},y)\in\hat{F}^{l(x)}\\}$ (1)

for any $x\in\Xi$, where $\sup$ is taken under partial ordering $x\subseteq y$
and $F^{l(x)}$ is the finite subset of elements of $\hat{F}$ enumerated in
$l(x)$ steps. Let $(x,\lambda)\in\hat{F}^{0}$ for every $x$. By definition for
modified operator, $l(\tilde{F}(x))\leq l(x)$ for each finite sequence $x$ and
$\tilde{F}(\omega)=F(\omega)$ for each infinite $\omega$, where
$\tilde{F}(\omega)=\sup_{n}\tilde{F}(\omega^{n})$. For any finite sequence $x$
the value of $\tilde{F}(x)$ is defined in $l(x)$ steps of computation.

We will use the uniformly computable sequence of all computable operators
$\\{F_{i}\\}$ such that given $i$ and $\omega$ some algorithm computes the
value $F_{i}(\omega)$ and for any computable operator $F$ there exists an $i$
such that $F(\omega)=F_{i}(\omega)$ for each $\omega$. This sequence is
defined by a recursively enumerable set $\cal F$ of triples $(i,x,y)$ such
that for any $i$ the set $\hat{F}=\\{(x,y):(i,x,y)\in{\cal F}\\}$ defines the
computable operator $F_{i}$ and for each computable operator $F$ an $i$ exists
such that $F=F_{i}$. We transform this sequence to a sequence
$\\{\tilde{F}_{i}\\}$ as it was done by (1).

A real-valued non-negative function $P:\Xi\to{\cal R}$ is called semimeasure
if

$\displaystyle P(\lambda)\leq 1,$ $\displaystyle P(x0)+P(x1)\leq P(x)$ (2)

for all $x\in\Xi$. We will consider lower semicomputable semimeasures $P$;
this means that the set $\\{(r,x):r\in{\cal Q},\ r<P(x)\\}$ is recursively
enumerable.

Solomonoff [18, 19] proposed ideas for defining the a priori probability
distribution on the basis of the general theory of algorithms. Levin in [26]
and [7] gives a precise form of Solomonoff’s ideas in a concept of a maximal
lower semicomputable semimeasure (see also Li and Vytanyi [9], Section 4.5.)
Levin proved that there exists the maximal to within a multiplicative positive
constant factor semimeasure $M$ semicomputable from below, i.e. for every
semimeasure $P$ semicomputable from below a positive constant $c$ exists such
that the inequality

$cM(x)\geq P(x)$ (3)

holds for all $x$. The semimeasure $M$ is called a priory or universal
semimeasure.

A function $P$ is a measure if (2) holds, where both inequality signs $\leq$
are replaced with the equality $=$. Any function $P$ satisfying (2) (with
equalities) can be extended on all Borel subsets of $\Omega$. Consider
intervals $\Gamma_{x}=\\{\omega\in\Omega:x\subseteq\omega\\}$ in $\Omega$ for
all $x\in\Xi$. The measure of any such interval can be defined as
$P(\Gamma_{x})=P(x)$ and can be extended to all Borel subsets of $\Omega$.

A measure $P$ is computable if there is an algorithm which for any $x\in\Xi$
outputs a rational approximation of the real number $P(x)$ with a given degree
of precision. A typical example of computable measure on $\Omega$ is the
uniform measure $L$, where $L(\Gamma_{x})=2^{-l(x)}$ for every $x\in\Xi$.

For technical reason, for any semimeasure $P$, we consider the maximal measure
$\bar{P}$ such that $\bar{P}\leq P$. This measure can be defined as

$\displaystyle\bar{P}(x)=\lim\limits_{n\to\infty}\sum\limits_{l(y)=n,x\subseteq
y}P(y)$

(see Levin and V’yugin [7]). In general, the measure $\bar{P}$ is non-
computable (and it is not a probability measure, since $\bar{P}(\Omega)<1$)
even then $P$ is a lower semicomputable semimeasure. From (3) the inequality
$c\bar{M}(A)\geq\bar{P}(A)$ follows for each lower semicomputable semimeasure
$P$ and for every Borel set $A$, where $c$ is a positive constant (the same as
in (3)). In particular, the measure $\bar{P}$ is absolutely continuous with
respect to the measure $\bar{M}$.

Following Levin [26, 7, 8] (see also V’yugin [22, 24]), the combinations of
probabilistic and deterministic processes is considered as the most general
class of processes for generating data. Any probabilistic process is defined
by some computable probability distribution. Any deterministic process is
realized by means of an algorithm. Algorithmic processes transform sequences
generated by probabilistic processes into new sequences. More precise, a
probabilistic computer is a pair $(P,F)$, where $P$ is a computable
probability distribution (for example, $P=L$) and $F$ is a Turing machine
supplied with an additional input tape. In the process of computation this
machine reads on this tape a sequence $\omega$ distributed according to $P$
and produces a sequence $\omega^{\prime}=F(\omega)$ (A correct definition see
in [26, 25, 22, 9]). So, we can compute the probability

$Q(x)=P\\{\omega:x\subseteq F(\omega)\\}$

of that the result $F(\omega)$ of the computation begins with a finite
sequence $x$. It is easy to see that $Q(x)$ is the lower semicomputable
semimeasure. Generally, the semimeasure $Q$ can be not a probability
distribution in $\Omega$, since $F(\omega)$ may be finite for some infinite
$\omega$.

The converse result is proved in Zvonkin and Levin [26]: for every lower
semicomputable semimeasure $Q(x)$ a probabilistic algorithm $(L,F)$ exists
such that

$Q(x)=L\\{\omega|x\subseteq F(\omega)\\},$

for all $x$, where $L(x)=2^{-l(x)}$ is the uniform probability distribution in
the set of all binary sequences.

Therefore, by (3) $M(x)$ defines an asymptotic universal upper bound of the
probability of generating $x$ by probabilistic algorithms.

A set of infinite sequences $U\subseteq\Omega$ is called open if it can be
represented as a union of a sequence of intervals $U=\cup\Gamma_{x_{i}}$,
where $x_{i}\in\Xi$ for $i=1,2,\dots$. An open set $U$ is effectively open if
the function $f(i)=x_{i}$ is total computable.

Let $P$ be a computable measure on $\Omega$. By Martin-Löf [10] test of
randomness with respect to the measure $P$ we mean a uniformly recursively
enumerable sequence $\\{U_{i}\\}$ of effectively open sets (i.e.,
$U_{i}=\cup_{j}\Gamma_{x_{i,j}}$ for each $i$ and the function
$f(i,j)=x_{i,j}$ is computable) such that $P(U_{i})\leq 2^{-i}$ for all $i$.
The null-set of any test is $\cap_{i}U_{i}$. From definition
$P(\cap_{i}U_{i})=0$. An infinite sequence $\omega\in\Omega$ is called Martin-
Löf random with respect to a computable measure $P$ if
$\omega\not\in\cap_{i}U_{i}$ for each test $\\{U_{i}\\}$ of randomness with
respect to $P$.

An equvalent definition of Martin-Löf randomness can be given in terms of the
a priory semimeasure. An infinite sequence $\omega$ is Martin-Löf random with
respect to a computable measure $P$ if and only if a positive constant $c$
exists such that

$\frac{P(\omega^{n})}{M(\omega^{n})}\geq c>0$ (4)

for every $n$ (see Zvonkin and Levin [26], [9]).

##  3 Algebra of LV-degrees

An infinite sequence $\alpha\in\Omega$ is Turing (or algorithmically)
reducible to an infinite sequence $\beta\in\Omega$ if $\alpha=F(\beta)$ for
some algorithmic operator $F$. Denote this as $\alpha\leq_{T}\beta$. Two
infinite sequences $\alpha$ and $\beta$ are Turing equivalent:
$\alpha\equiv_{T}\beta$, if each of them reducible to another one. The classes
of equivalent sequences form Turing degrees.

A Borel set $A\subseteq\Omega$ is called algorithmically (or Turing) invariant
if it is together with each sequence also contains all algorithmically
equivalent sequences. In other words, the set $A$ can be represented as the
union of Turing degrees. For any set $A\subseteq\Omega$, let
$\bar{A}=\\{\omega:\exists\alpha(\alpha\in A\&\alpha\equiv_{T}\omega)\\}$ be
the algorithmic closure the set $A$.

Martin-Löf random sequences should serve as mathematical analogs of sequences
which can be obtained in stochastic processes. On the other hand, some
infinite Martin-Löf random sequences can be defined using exact mathematical
constructions, that contradicts to our intuition. For example, the binary
representation of the Chaitin number $\sum_{n}2^{-{\rm KP}(n)}$, where ${\rm
KP}(n)$ is the prefix Kolmogorov complexity of a positive integer number $n$,
is Martin-Löf random with respect to uniform measure on $\Omega$ (see [25]),
another example of the exact mathematical construction of Martin-Löf random
sequence can be found in Zvonkin and Levin [26]. These examples show that some
correction is needed in the interpretation of the concept of a random
sequence.

By de Leeuw–Moore–Shannon–Shapiro theorem $\bar{M}(\\{\alpha\\})=0$, where
$\alpha$ is any non-computable sequence (Leeuw et al. [6], see also Sacks
[14]). In particular, the Chaitin number, or rather, its binary representation
$\alpha$, cannot be output (with a positive probability) of any probabilistic
algorithm. Similarly, any individual random sequence $\alpha$, defined by a
mathematical construction, cannot be obtained as output in any combination of
random and algorithmic processes.

Let any property ${\cal A}$ defines a Borel set $A=\\{\omega\in\Omega:{\cal
A}(\omega)\\}$ such that $\bar{M}(A)=0$. Then for any probabilistic machine
$(L,F)$, the probability $P(A)=L\\{\omega:F(\omega)\in A\\}$ of generation a
sequence from $A$ is equal 0. We call such sets negligible. A set $A$ is
negligible if and only if $L(F^{-1}(A))=0$ for each computable operator $F$,
where $F^{-1}(A)=\\{\omega\in\Omega:F(\omega)\in A\\}$ (see [7, 22]).

We consider algorithmic transformations of infinite sequences, which can be
carried out using probabilistic algorithms. By definition any infinite
sequence from the negligible set cannot be obtained (with positive
probability) in any combination of stochastic and algorithmic processes.

For example, for any non-computable infinite sequence $\alpha$ the set

$\\{\omega\in\Omega:\exists F(F(\omega)=\alpha)\\}$

is negligible.

Let ${\cal B}$ be the Boolean algebra of all algorithmically invariant Borel
subsets (collections of infinite binary sequences) of $\Omega$. We identify
any two sets from ${\cal B}$ which differ by a negligible set. More correctly,
let us consider the equivalence relation on ${\cal B}$

$A\sim B\Longleftrightarrow\bar{M}((A\setminus B)\cup(B\setminus A))=0.$

Let $\Upsilon$ be the factor algebra of ${\cal B}$ by the equivalence relation
$\sim$. Denote the equivalence class of any set $A$ by ${\bf a}=[A]$. The
elements of $\Upsilon$ will be called degrees of randomized computability or
LV-degrees.111V’yugin [22] called $\Upsilon$ the algebra of invariant
properties, this algebra was recently called by Bienvenu and Patey [1] and in
Holzl and Porter [4] the algebra of Levin-V’yugin degrees (or LV-degrees).

Define, for any lower semicomputable semimeasure $P$, $\bar{P}({\bf
a})=\bar{P}(A)$. Define the Boolean operations on $\Upsilon$: ${\bf a}\cup{\bf
b}=[A\cup B]$ and ${\bf a}\cap{\bf b}=[A\cap B]$, where ${\bf a}=[A]$ and
${\bf b}=[B]$. The partial ordering on $\Upsilon$ is defined:

${\bf a}\preceq{\bf b}\Longleftrightarrow\bar{M}(A\setminus B)=0.$

In what follows, we call standard any sequence which is algorithmically
equivalent to a sequence Martin-Löf random with respect to some computable
measure. By definition, any computable measure of the set of all standard
sequences is equal to 1.

Zvonkin and Levin [26] (Theorem 3.1) proved that any sequence $\omega$ Martin-
Löf random with respect to a computable measure is computable or
algorithmically equivalent to a sequence which is Martin-Löf random with
respect to the uniform measure.

Therefore, the elements ${\bf r}=[\bar{R}]$ and ${\bf c}=[C]$ arise naturally,
where $R$ be the set of all sequences Martin-Löf random with respect to
uniform measure, $\bar{R}$ be its algorithmic closure. In particular, the set
$\bar{R}$ contains all non-computable sequences random with respect to
computable measures (and all sequences Turing equivalent to such sequences),
Let $C$ be the set of all computable sequences. Evidently, $\bar{M}({\bf
r})>0$ and $\bar{M}({\bf c})>0$.

The zero element 0 of the algebra $\Upsilon$ is the equivalence class of the
empty set. It consists of all algorithmically invariant negligible Borel
subsets of $\Omega$, $\bar{M}({\bf 0})=0$. The maximal element of $\Upsilon$
is ${\bf 1}=[\Omega]$.

By definition ${\bf d}$ is an atom of $\Upsilon$ if $\bf d\not=\bf 0$ and it
cannot be represented as ${\bf d}={\bf a}\cup{\bf b}$, where ${\bf a}\cap{\bf
b}={\bf 0}$, ${\bf a}\not={\bf 0}$ and ${\bf b}\not={\bf 0}$.

It was first pointed in Levin and V’yugin [7] that ${\bf r}$ and $\bf c$ are
atoms of $\Upsilon$. The proof of this result (which attributes to Levin) was
first given in V’yugin [22]. Holzl and Porter [4] also presented the careful
proof of this result. We present a short proof for completeness of
presentation.

###### Theorem 1

The element ${\bf r}$ is an atom of $\Upsilon$.

Proof. Assume that ${\bf r}={\bf a}\cup{\bf b}$, where ${\bf a}\cap{\bf
b}={\bf 0}$, ${\bf a}\not={\bf 0}$ and ${\bf b}\not={\bf 0}$. Then
$\bar{R}=A\cup B$, where ${\bf a}=[A]$ and ${\bf b}=[B]$, where $A$ and $B$
are the algorithmically invariant sets of infinite sequences. We can assume
without loss of generality that $A\cap B=\emptyset$. Recall that $R$ is the
set of all Martin-Löf random sequences with respect to the uniform measure.
Let $A^{\prime}=A\cap R$ and $B^{\prime}=B\cap R$. Since any sequence
$\alpha\in A$ is algorithmically equivalent to some sequence from $A^{\prime}$
and $\bar{M}(A)>0$, $\bar{M}(A^{\prime})>0$ follows. Analogously
$\bar{M}(B^{\prime})>0$.

Let $P$ be a probability measure on $\Omega$ absolutely continuous with
respect to $\bar{M}$, i.e., $\bar{M}(X)=0$ implies $P(X)=0$ for each Borel set
$X$.

Let $\frac{dP}{d\bar{M}}(\omega)$ be the Radon–Nicodym derivative of $P$ by
the measure $\bar{M}$, where $P$ is a probability measure on $\Omega$
absolutely continuous with respect to the measure $\bar{M}$. By definition

$P(X)=\int\limits_{X}\frac{dP}{d\bar{M}}(\omega)d\bar{M}$ (5)

for each Borel set $X$. In particular, (5) holds true for each computable
measure $P$ and for the measure $\bar{P}$, where $P$ is a lower semicomputable
semimeasure.

###### Lemma 1

Let a measure $P$ is absolutely continuous with respect to the measure
$\bar{M}$, $A\subseteq\Omega$ and $\frac{dP}{d\bar{M}}(\omega)>0$ for each
$\omega\in A$. Then $P(A)=0$ implies $\bar{M}(A)=0$.

Proof. By (5), $P(A)=\int\limits_{A}\frac{dP}{d\bar{M}}(\omega)d\bar{M}$. It
is easy to prove that if $\frac{dP}{d\bar{M}}(\omega)>0$ for each $\omega\in
A$ and $P(A)=0$ then $\bar{M}(A)=0$. $\Box$

###### Corollary 1

Let $P$ be a computable measure and $A$ consists of $P$-random sequences. Then
$P(A)=0$ implies $\bar{M}(A)=0$.

Proof. For any random sequence $\omega$

$P(\omega^{n})/\bar{M}(\omega^{n})\geq P(\omega^{n})/M(\omega^{n})\geq c>0$

holds for every $n$, where $c$ is a constant depending on $\omega$. Then
$\frac{dP}{d\bar{M}}(\omega)\not=0$ for each $\omega\in A$. By Lemma 1
$\bar{M}(A)=0$. $\Box$

Let us finish the proof of the theorem. If an infinite sequence $\omega$ is
random with respect to the uniform measure then any sequence
$\omega^{\prime}$, which differs from it in a finite number of bits, is also
random. Then $\omega,\omega^{\prime}\in R$. Besides,
$\omega\equiv_{T}\omega^{\prime}$.

We can choose algorithmically invariant Borel sets $A$ and $B$ such that any
two sequences $\alpha\in A$ and $\beta\in B$ are not algorithmically
equivalent. Let $A^{\prime}=A\cap R$ and $B^{\prime}=B\cap R$. Then
$\omega,\omega^{\prime}\in A^{\prime}$ or $\omega,\omega^{\prime}\in
B^{\prime}$, By Corollary 1 $\bar{M}(A^{\prime})>0$ implies $L(A^{\prime})>0$.
Analogously $\bar{M}(B^{\prime})>0$ implies $L(B^{\prime})>0$.

We apply the Kolmogorov 0 or 1 law to the sequence $f_{1},f_{2},\dots$ of
random variables, where $f_{i}(\omega)=\omega_{i}$ are random variables
defined on the probability space $(\Omega,L)$. It follows from invariant
property of the sets $A^{\prime}$ and $B^{\prime}$ that for each $n$ they
belong to $\sigma$-algebra generated by random variables $f_{n},f_{n+1},\dots$
and then they belong to the residual $\sigma$-algebra of $f_{1},f_{2},\dots$.
By Kolmogorov 0 or 1 law $L(A^{\prime})=0$ or $L(A^{\prime})=1$ and the same
holds for $B^{\prime}$. This is a contradiction, since $A^{\prime}\cap
B^{\prime}=\emptyset$ and $L(A^{\prime})>0$, $L(B^{\prime})>0$. Therefore,
$\bf r$ is an atom of $\Upsilon$. $\Box$

Evidently, $\bf c$ is also an atom of $\Upsilon$. It is easy to see that $\bf
r$ is the single atom of the uniform measure 1.

The atoms $\bf c$ and $\bf r$ be generated by the standard sequences. A
question arises does ${\bf 1}={\bf c}\cup{\bf r}$?222This would mean that all
sequences (information) that can be generated using probabilistic algorithms
are stochastic or computable. We prove in Section 5.1 that ${\bf
1}\setminus({\bf c}\cup{\bf r})\not={\bf 0}$ and, moreover, we prove in
Section 5.5 that there exists an infinite sequence of other atoms.

It is easy to show that the set of all atoms of the algebra $\Upsilon$ is at
most countable. To do this, choose for each atom ${\bf a}=[A]$ a union $D_{a}$
of a finite number of intervals such that

$\bar{M}((A\setminus D_{a})\cup(D_{a}\setminus A))<(1/4)\bar{M}(\bf a).$

If $\bf a\not=\bf b$ then $D_{a}\not=D_{b}$. The set of all $D_{a}$ is at most
countable.

We will prove in Section 5.5 that the set of all atoms is countable. Let ${\bf
a}_{1},{\bf a}_{2},{\bf a}_{3},\dots$ be all atoms of $\Upsilon$, where ${\bf
a}_{1}={\bf c}$ and ${\bf a}_{2}={\bf r}$ and the atoms

$\bf c$ and $\bf r$ are defined by standard sequences. We will also prove that
the algebra $\Upsilon$ is not limited to atoms only: ${\bf
1}\setminus\bigcup_{i=1^{\infty}}{\bf a}_{i})\not={\bf 0}$. By definition the
element ${\bf e}={\bf 1}\setminus\bigcup_{i=1}^{\infty}{\bf a}_{i}$ is
infinitely divisible, i.e. for any non-zero element ${\bf x}\subseteq{\bf e}$
a decomposition ${\bf x}={\bf x}_{1}\cup{\bf x}_{2}$ exists, where ${\bf
x}_{1}\cap{\bf x}_{2}={\bf 0}$, ${\bf x}_{1}\not={\bf 0}$ and ${\bf
x}_{2}\not={\bf 0}$.

Theorems 3 and 6 given below in Sections 5.2 and 5.5 will imply the main
result of this paper on decomposition of the maximal element of LV-algebra:

The decomposition of the maximal element of $\Upsilon$ take place:

${\bf 1}=\cup_{i=1}^{\infty}{\bf a}_{i}\cup{\bf e},$ (6)

where ${\bf a}_{1},{\bf a}_{2},\dots$ are all atoms of $\Upsilon$ and ${\bf
e}$ is a non-zero infinitely divisible element.

The decomposition (6) shows that any non-zero LV-degree can be represented as
a union of some atoms or it is an infinitely divisible element, or it is a
union of some atoms and non-zero infinitely divisible element.

We show in Theorem 9 given below in Section 5.6 that the similar to (6)
nontrivial decomposition take place for LV-degree of all hyperimmune
sequences:333i.e., for indicator sequences of the hyperimmune sets of integer
numbers.

${\bf h}=\cup_{i=1}^{\infty}{\bf h}_{i}\cup{\bf e},$ (7)

where ${\bf h}_{1},{\bf h}_{2},\dots$ are atoms and ${\bf e}$ is a non-zero
infinitely divisible element generated by hyperimmune degrees.

##  4 Network flows

To construct the elements $\Upsilon$ generated by non-standard sequences, we
have to construct lower semicomputable semimeasures $P$ such that
$\bar{P}(\Omega\setminus(\bar{R}\cup C))>0$.

We will construct some such semimeasure $P$ which will be represented as a
flow over a certain network.

We will consider the set $\Xi$ of all finite binary sequences as a graph
(tree) whose vertices are sequences $x\in\Xi$ connected by edges of unit
length $(x,x0)$, $(x,x1)$. During the construction, we will add extra edges
$(x,y)$, where $x,y\in\Xi$, $x\subset y$, of length $l(y)-l(x)>1$. For any
edge $\sigma=(x,y)$ denote by $\sigma_{1}=x$ its starting vertex, and by
$\sigma_{2}=y$ its final vertex. A function $q(\sigma)$, which is defined on
all edges of unit length as well as on all extra edges, is called network if

$\sum\limits_{\sigma:\sigma_{1}=x}q(\sigma)\leq 1$ (8)

for each $x\in\Xi$. By $q$-flow we mean the minimal semimeasure $P$ such that
$P\geq R$, where the function $R$ (frame of the network flow) is defined as
follows:

$\displaystyle R(\lambda)=1,$ (9) $\displaystyle
R(y)=\sum\limits_{\sigma:\sigma_{2}=y}q(\sigma)R(\sigma_{1})$ (10)

for $y\not=\lambda$ (empty sequence).

It is easy to verify that the semimeasure $P$ can be defined as

$\displaystyle P(\lambda)=1,$ (11) $\displaystyle
P(y)=\sum\limits_{\sigma:\sigma_{1}\subset
y\subseteq\sigma_{2}}q(\sigma)R(\sigma_{1})$ (12)

for each $y$. The value $q(\sigma)$ can be interpreted as a portion of the
flow that goes from $x=\sigma_{1}$ to the vertex $y=\sigma_{2}$ along the edge
$\sigma$.

We associate with any network $q$ the flow-delay function

$s(x)=1-q(x,x0)-q(x,x1).$

A network $q$ is called elementary if there exists an $n$ such that $s(x)$ is
defined for all $x$, $l(x)\leq n$, the set $G^{n}$ of all extra edges is
finite and $l(\sigma_{2})\leq n$ for each $\sigma\in G^{n}$. We assume that
$q(x,x0)=q(x,x1)=\frac{1}{2}(1-s(x))$ for both edges of unit length outgoing
from $x$.

Any elementary network is a constructive object. We will define a sequence of
elementary networks gradually increasing $n$.

###  4.1 Template 1

We present the construction of a network $q$ depending on a recursive
predicate $B(i,\sigma)$, where $i$ is a positive integer number (task number),
$\sigma$ is an extra edge.

Let $p:{\cal N}\to{\cal N}$ be a total computable function such that for any
$i$, $p(n)=i$ for infinitely many $n$.444This function can be defined as
follows. Let $\langle i,j\rangle$ denotes the order number of any pair $(i,j)$
of positive integer numbers under some one-to-one corresponding between all
positive integer numbers and all such pairs. Define $p(\langle i,j\rangle)=i$
for all $(i,j)$.

Any extra edge $\sigma$ will refer to some task $i$ so that
$p(l(\sigma_{1}))=p(l(\sigma_{2}))=i$. We say that the edge $\sigma$ is of
$i$th type. The goal of the task $i$ will be to draw extra edges $\sigma$ such
that $B(i,\sigma)$ is satisfied and that each infinite sequence $\omega$
passes through one of these edges or the delay function would be equal to 1 on
some initial fragment of $\omega$.555An infinite sequence $\omega$ passes
through the edge $\sigma$ if $\sigma_{2}\subset\omega$.

We associate with the predicate $B$ the function of setting an extra edge

$\beta(x,n)=\min\\{y:l(y)=n,p(l(y))=p(l(x)),B(p(l(x)),(x,y))\\}.$ (13)

Here $\min$ is taken with respect to the natural linear orderings of all
finite binary sequences. We suppose that $\min\emptyset$ is undefined. The
pair $(x,\beta(x,n))$ will be drawn in $G$ as an extra edge.

Define a sequence of elementary networks by the mathematical induction on $n$.

Define $s(\lambda)=0$ and $G^{0}=\emptyset$.

Let $n\geq 1$ and $G^{n-1}$ and $q(\sigma)$ be defined for every $\sigma\in
G^{n-1}$, $s(x)$ be defined and for every $x$ such that $l(x)\leq n-1$, and
$q(\sigma)=\frac{1}{2}(1-s(\sigma_{1})$ for each $\sigma$ of unit length such
that $l(\sigma_{2})=n$.

Let $G^{n-1}(i)$ be the set of all extra edges drawn by the task $i$ at steps
$<n$. It should be $p(l(\sigma_{1}))=p(l(\sigma_{2}))=i$ for each $\sigma\in
G^{n-1}(i)$.

We first introduce an auxiliary function $w(i,n)$. The value of $w(i,n)$ is
equal to the smallest $m$ such that $m\leq n$, $p(m)=i$ and $m>l(\sigma_{2})$
for each extra edge $\sigma\in G^{n-1}(j)$ where $j<i$, i.e., for any extra
edge $\sigma$ drawn during the processing of any task $j<i$. Let us give the
exact definition:

$\displaystyle w(i,n)=\min\\{m:m\leq n\&p(m)=i\&$ $\displaystyle\forall
j\forall\sigma((j<i\&\sigma\in G^{n-1}(j)\rightarrow m>l(\sigma_{2})).$ (14)

We refer to $w(i,n)$ as to the initial step of a session for executing the
task $i$.

The change in the value: $w(i,n)\not=w(i,n-1)$, may occur due to the fact that
at step $n$ some task $j<i$ draws its extra edge above the level $w(i,n-1)$,
and thus violates the condition for the definition of $w(i,n-1)$.666By
construction, if at a step $n$ of the induction some task draw a new extra
edge $\sigma$ then $l(\sigma_{2})=n$.  Lemma 4 will show that this violation
will occur at no more than a finite number of construction steps.

We will use a function $\rho(n)$ which is a parameter of the construction, put
$\rho(n)=(n+3)^{2}$.

The construction of step $n$ splits into three cases. Let $i=p(n)$.

Case 1. $w(p(n),n)=n$ (starting a new session for executing the task $i=p(n)$:
installing or reinstalling the task $i$).

In this case define $s(y)=1/\rho(n)$ for every $y$ such that $l(y)=n$ and set
$G^{n}=G^{n-1}$.

Case 2. $w(i,n)<n$ and $C_{n}(i)\not=\emptyset$, where $C_{n}(i)$ is the set
of all sequences $x$ that require processing, i.e., such that $p(l(x))=i$,
$w(i,n)\leq l(x)<n$, $s(x)>0$, $\beta(x,n)$ is defined and no extra edge in
$G^{n-1}$ outgoes from $x$ (processing step of the task $i$).

In this case define $G^{n}=G^{n-1}\cup\\{(x,\beta(x,n)):x\in C_{n}(i)\\}$ and
$q((x,\beta(x,n)))=s(x)$ for each $x\in C_{n}(i)$.

If $s(x)<1$ then define $s(\beta(x,n))=0$ and $s(y)=s(x)/(1-s(x))$ for all
other $y$ of length $n$ such that $x\subset y$ and $y\not=\beta(x,n)$.

If $s(x)=1$ then define $s(y)=0$ for every $y$ such that $x\subset y$ and
$l(y)=n$.

Define $s(y)=0$ for all other $y$ of length $n$.

Case 3. Cases 1 and 2 do not occur. In this case define $s(x)=0$ for all $x$
of length $n$ and $G^{n}=G^{n-1}$.

After all, define $q(\sigma)=\frac{1}{2}(1-s(\sigma_{1}))$ for each $\sigma$
of unit length such that $l(\sigma_{1})=n$.

This concludes the description of the induction step.

Define $G=\cup_{n}G^{n}$ and $G(i)=\cup_{n}G^{n}(i)$ for any $i$. By the
construction $s(x)$ is defined for each $x$ and $0\leq s(x)\leq 1$,
$q(\sigma)$ is defined for each $\sigma\in G$ and
$q(\sigma)=\frac{1}{2}(1-s(\sigma_{1})$ for each $\sigma$ of unit length.

Lemmas 2–3 below present the simplest properties of the construction.

###### Lemma 2

The values of the flow delay function $s$ are $0$ or rational numbers of type
$\frac{1}{M}$, where $M$ is a positive integer number.

Proof. By Case 1 at step $n$ we define $s(x)=\frac{1}{\rho(n)}$ for each $x$
such that $l(x)=n$. By induction on $n$, in Case 2 if $s(x)=\frac{1}{M}$ for
some $M>1$ then $s(y)=\frac{1}{M-1}$ for each $y$ such that $x\subset y$ and
$y\not=\beta(x,n)$, also, $s(\beta(x,n))=0$. If $s(x)=1$ then $s(y)=0$ for
each $y$ such that $x\subset y$ and $l(y)=n$. $\Box$

The $q$-flow $P$ is lower semicomputable semimeasure by definition (11)–(12).

###### Lemma 3

There cannot be two overlapping extra edges $(x,y),(x^{\prime},y^{\prime})\in
G$ such that $x^{\prime}\subset x\subset y^{\prime}$ and $l(y^{\prime})<l(y)$.

Proof. Assume that such a pair of overlapping extra edges exists. Let
$i=p(l(x))$ and $i^{\prime}=p(l(x^{\prime}))$. Evidently $i\not=i^{\prime}$.
By the construction the extra edge $(x^{\prime},y^{\prime})$ was drawn at step
$n^{\prime}=l(y^{\prime})$ and the extra edge $(x,y)$ was drawn at the later
step step $n=l(y)$, where $n>n^{\prime}$ and $i<i^{\prime}$.

There are two mutually exclusive cases. If
$n^{\prime\prime}=l(x)=w(i,n^{\prime\prime})$, i.e., the task $i$ was
installed (or reinstalled) at the step $n^{\prime\prime}$. Then the pair
$(x^{\prime},y^{\prime})$ cannot be an extra edge, since it should be added to
$G$ at the later step $n^{\prime}>n^{\prime\prime}$ by the task
$i^{\prime}>i$, that leads to the contradiction.

Assume that $n^{\prime\prime}=l(x)>w(i,n^{\prime\prime})$, i.e., the task $i$
is processed at step $n^{\prime\prime}$. Then Case 2 holds at step $n$ and
$s(x)>0$. In this case, some extra edge $\sigma$ such that
$l(\sigma_{2})=n^{\prime\prime}$ have to be drawn by the task $i$ at the step
$n^{\prime\prime}$. Then the contradiction is obtained, since the extra edge
$(x^{\prime},y^{\prime})$ should be added to $G$ at the later step
$n^{\prime}>n^{\prime\prime}$ by the task $i^{\prime}>i$. The resulting
contradiction proves the lemma. $\Box$

The next lemma shows that each task leads to the installation of new extra
edges only at a finite number of steps.

By construction $w(i,n+1)\geq w(i,n)$ for every $n$. Let
$w(i)=\lim_{n\to\infty}w(i,n)$.

###### Lemma 4

$G(i)$ is finite and $w(i)<\infty$ for each $i$.

Proof. Note that if $G(j)$ is finite for every $j<i$, then $w(i)<\infty$.
Therefore, it suffices to prove that $G(i)$ is finite for each $i$. Assume the
opposite. Let $i$ be the minimal for which $G(i)$ is infinite. Since $G(j)$ is
finite for each $j<i$, $w(i)<\infty$.

For any $x$ such that $l(x)\geq w(i)$, let $k$ be the maximal such that
$\sigma_{1}=x^{k}$ and $l(\sigma_{2})\leq l(x)$ for some edge $\sigma\in
G(i)$. This extra edge can be drawn by Case 2, where $s(x^{k})>0$. By Lemma 2
$s(x^{k})=1/M$, where $M$ is an integer number such that $M\geq 1$. If no such
edge exists then set $k=w(i)$. Define

$K(x)=\left\\{\begin{array}[]{l}\rho(w(i))\mbox{ if }l(x)\leq w(i)\mbox{ or
}k=w(i),\\\ M-1\mbox{ if }l(x)>w(i)\mbox{ and }k>w(i),\mbox{ where
}s(x^{k})=1/M.\\\ \end{array}\right.$

Since $K(x)\geq K(y)$ for every $x$ and $y$ such that $x\subset y$, and,
moreover, if $K(x)>K(y)$ then $K(x)>K(z)$ for each $z$ such that $x\subset z$
and $l(z)=l(y)$, the function

$\hat{K}(\omega)=\min\\{n:\forall k\geq n(K(\omega^{k})=K(\omega^{n}))\\}$

is defined for each infinite $\omega\in\Omega$ and it is continuous. Since
$\Omega$ is compact, it is upper bounded by some number $m$. Then
$K(x)=K(x^{m})$ for every $x$ such that $l(x)\geq m$.

If at some step $n\geq m$ an extra edge $\sigma$ will be drawn by task $i$,
where $l(\sigma_{1})>m$, then by Case 2 $K(y)<K(\sigma_{1})$ for every $y$ of
length $n$ such that $\sigma_{1}\subset y$. Therefore, the existence of such
$m$ contradicts to the assumption of infinity of $G(i)$. The lemma is proved.
$\Box$

The support set of a semimeasure $P$ is defined as

$E_{P}=\\{\omega\in\Omega:\forall n(P(\omega^{n})>0)\\}.$

It is easy to see that $\bar{P}(E_{P})=\bar{P}(\Omega)$.

A sequence $\alpha\in\Omega$ is called $i$-extension of a finite sequence $x$
if $x\subset\alpha$ and $B(i,(x,\alpha^{n}))$ is satisfied for almost all $n$.

Note that if $\sigma\in G(i)$ is an extra edge of the $i$th type then
$B(i,\sigma)$ is satisfied.

###### Lemma 5

Let $\omega\in E_{P}$ and for any initial fragment $\omega^{n}$ of the
sequence $\omega$ there is an $i$-extension. Then $\omega$ passes through an
extra edge of the $i$th type (i.e., $\sigma_{2}\subset\omega$ for some
$\sigma\in G(i)$).

Proof. By definition $P(\omega^{n})\not=0$ for all $n$. By Lemma 4, there is a
maximal $m$ such that $p(m)=i$ and $s(\omega^{m})>0$. Since $\omega^{m}$ has
an $i$-extension and $s(\omega^{m})>0$, by Case 2 of the construction, an
extra edge $(\omega^{m},y)$ will be drawn on some step $n$, where $l(y)=n$.
Assume that $y\not\subset\omega$. If $s(\omega^{m})<1$ then $s(\omega^{n})>0$
that contradicts to the choice of $m$. Let $s(\omega^{m})=1$. Since $m\geq
w(i,n)$ and by Lemma 3, no extra edge $\sigma$ exists such that
$\sigma_{1}\subset\omega^{m}\subset\sigma_{2}$. Then $P(\omega^{m+1})=0$ that
is a contradiction with the assumption of the lemma. Hence, $y\subset\omega$.
$\Box$

A semimeasure $P$ is continuous if $\lim\limits_{n\to\infty}P(\omega^{n})=0$
for each infinite sequence $\omega$. We give some sufficient condition for the
continuity of the $q$-network flow $P$.

A number $n$ separates the set $D$ of edges if $l(\sigma_{1})\geq n$ or
$l(\sigma_{2})<n$ for each edge $\sigma\in D$.

###### Lemma 6

Let $q$ be a network. The $q$-flow is continuous if the set of extra edges is
separated by an infinite set of numbers, and $q(x,x0)=q(x,x1)$ for each
$x\in\Xi$.

Proof. Let $P$ be the $q$-flow and a number $n$ separates the set of extra
edges. Then

$P(x)=R(x)=q(x^{n-1},x)R(x^{n-1})\leq q(x^{n-1},x)P(x^{n-1})$

for each $x$ of length $n$. By (8) and by the assumption of the lemma
$q(x^{n-1},x)\leq 1/2$ for all $x$ and $n$. Then
$P(\omega^{n})\leq(1/2)P(\omega^{n-1})$ for each $n$ separating the set of
extra edges. Since there are infinitely many of such $n$, we have
$\lim\limits_{n\to\infty}P(\omega^{n})=0$, i.e., the semimeasure $P$ is
continuous. $\Box$

The following corollary of Lemma 6 takes place.

###### Corollary 2

Let $P$ be the flow through the network $q$ defined by Template 1. Then the
semimeasure $P$ is continuous.

Proof. To apply Lemma 6 to the semimeasure $P$, it suffices to note that the
number $w(i)$ separates $G$ for each $i$. $\Box$

###### Lemma 7

$\bar{P}({\bf 1})>0$.

Proof. Let us estimate $\bar{P}(\Omega)$ from below. Let $i=p(n)$. Define

$S_{n}=\sum\limits_{u:l(u)=n}R(u)-\sum\limits_{\sigma:\sigma\in
G,l(\sigma_{2})=n}q(\sigma)R(\sigma_{1}).$

From the definition of the frame,

$\displaystyle\sum\limits_{u:l(u)=n+1}R(u)=\sum\limits_{u:l(u)=n}(1-s(u))R(u)+\sum\limits_{\sigma:\sigma\in
G,l(\sigma_{2})=n+1}q(\sigma)R(\sigma_{1}).$ (15)

Consider the case where $w(p(n),n)<n$.

If there is no edge $\sigma\in G$ such that $\sigma_{1}\in C_{n}(i)$ and
$l(\sigma_{2})=n$, then $S_{n+1}\geq S_{n}$. Now, let
$C_{n}(i)\not=\emptyset$. Define

$\Phi(\sigma,u)\Longleftrightarrow\sigma_{1}\in
C_{n}(i)\&l(\sigma_{2})=l(u)\&\sigma_{1}\subseteq u\&u\not=\sigma_{2}.$

If $s(\sigma_{1})=1$ for $\sigma_{1}\in C_{n}(i)$ then
$\sum\limits_{u:l(u)=n,\sigma_{1}\subseteq u}s(u)R(u)=0$.

By the construction, the value $s(x)$ defines a portion of the delayed flow in
the vertex $x$. The rest portion $1-s(x)$ of the flow goes equally to the
vertices $x0$ and $x1$. The portion $s(x)$ of the delayed flow can be later
directed to some $y$ such that $l(y)=n$ and $x\subset y$ only by Case 2 along
an extra edge $(x,y)$, where $y=\beta(x,n)$ outgoing from $x$ and drawn on the
step $n$. We will show that at step $n$ the portion of the newly delayed flow
in all $u$ of length $n$ such that $x\subseteq u$ and $u\not=y$ does not
exceed the portion of the previously delayed flow at the vertex $x$ and
directed along the edge $(x,y)$, this part of the flow is no longer delayed by
the task $i$ in the current session.

The following chain of equalities and inequalities take place:

$\displaystyle\sum\limits_{u:l(u)=n}s(u)R(u)=$
$\displaystyle\sum\limits_{\sigma:\sigma_{1}\in
C_{n}(i),s(\sigma_{1})<1}\sum\limits_{u:l(u)=n,\sigma_{1}\subseteq
u}s(u)R(u)=$ $\displaystyle\sum\limits_{\sigma:\sigma_{1}\in
C_{n}(i),s(\sigma_{1})<1}s(\sigma_{2})\sum\limits_{u:\Phi(\sigma,u)}R(u)=$
$\displaystyle\sum\limits_{\sigma:\sigma_{1}\in
C_{n}(i),s(\sigma_{1})<1}\frac{s(\sigma_{1})}{1-s(\sigma_{1})}\sum\limits_{u:\Phi(\sigma,u)}R(u)\leq$
$\displaystyle\sum\limits_{\sigma:\sigma_{1}\in
C_{n}(i),s(\sigma_{1})<1}s(\sigma_{1})R(\sigma_{1})=$
$\displaystyle\sum\limits_{\sigma:\sigma_{1}\in
C_{n}(i),s(\sigma_{1})<1}q(\sigma)R(\sigma_{1})=$
$\displaystyle\sum\limits_{\sigma:\sigma\in
G,l(\sigma_{2})=n}q(\sigma)R(\sigma_{1}).$ (16)

Here we have used the inequality

$\sum\limits_{u:\Phi(\sigma,u)}R(u)\leq(1-s(\sigma_{1}))R(\sigma_{1})$ (17)

for each $\sigma\in G^{n}$ such that $\sigma_{1}\in C_{n}(i)$ and
$s(\sigma_{1})<1$. Inequality (17) takes place, since the sum on the left is
equal to the flow through the set of vertices $\\{u:\Phi(\sigma,u)\\}$, and
the value from the right-hand side of the inequality is equal to the value of
the flow outgoing from the vertex $\sigma_{1}$, except for its part passing
through an extra edge $\sigma$. By Lemma 3 there cannot be an edge
$\sigma^{\prime}\in G$ overlapping with $\sigma$, i.e., such that
$\sigma^{\prime}_{1}\subset\sigma_{1}\subset\sigma^{\prime}_{2}$ and
$l(\sigma^{\prime}_{2})<l(\sigma_{2})$. Therefore, no extra portion of the
flow from some vertex $\sigma^{\prime}_{1}\subset\sigma_{1}$ cannot go through
$\sigma_{1}$ and thus increase the flow to $\\{u:\Phi(\sigma,u)\\}$.

Combining the resulting estimate with (15), we get $S_{n+1}\geq S_{n}$.

Consider now the case where $w(p(n),n)=n$. Then

$\sum\limits_{u:l(u)=n}s(u)R(u)\leq 1/\rho(n)=1/(n+3)^{2}.$

Combining this inequality with (15), we get $S_{n+1}\geq S_{n}-1/(n+3)^{2}$.
From here and from $S_{0}=1$ we get

$S_{n}\geq 1-\sum\limits_{i=1}^{\infty}1/(i+3)^{2}\geq\frac{1}{2}$

for all $n$. Since $P\geq R$,

$\bar{P}(\Omega)=\inf\limits_{n}\sum\limits_{l(u)=n}P(u)\geq\inf\limits_{n}S_{n}\geq\frac{1}{2}.$

The lemma is proved. $\Box$

##  5 Applications of Template 1

In this section we present two applications of Template 1.

###  5.1 Nonstochastic Turing degrees

We will prove that ${\bf 1}\setminus({\bf r}\cup{\bf c})\not={\bf 0}$.

Let $\\{F_{i}\\}$ be the uniformly computable sequence of all computable
operators We will assume that this sequence is modified by (1) of Section 2
such that some output $\tilde{F}_{(}x)\subseteq F_{i}(x)$ is obtained in
$l(x)$ steps of computation and the length of this output does not exceed the
length $l(x)$ of the input $x$, $\tilde{F}_{i}(\omega)=F_{i}(\omega)$ for each
infinite $\omega$.

We also assume that for any computable operator $F$ there are infinitely many
$i$ such that $F_{i}=F$.777To define such a sequence, redefine a sequence of
all computable operators $F_{i}$ as follows. For any $i$, define
$F^{\prime}_{\langle i,j\rangle}=F_{i}$ for all $j$. As before, the new
sequence of operators will be denoted by $F_{i}$. Thus, for any number $i$ of
a computable operator $F_{i}$, one can enumerate an infinite sequence of its
other numbers.

Define

$\displaystyle B(i,\sigma)\Longleftrightarrow
l(\tilde{F}_{i}(\sigma_{2}))>\sigma_{1}+i,$

where $\tilde{F}_{i}$ is the modified by (1) computable operator and the
finite sequence $\sigma_{1}$ (the starting point of the edge $\sigma$) is
identified with its number in the natural numbering of the set $\Xi$.

###### Theorem 2

For any infinite sequence $\omega$ from the support set of the semimeasure $P$
and for any computable operator $F$, if $F(\omega)$ is infinite then the
sequence $F(\omega)$ is not Martin-Löf random with respect to the uniform
measure.

Proof. Note that if $F(\omega)$ is infinite and $F_{i}=F$, then for each
initial fragment of the sequence $\omega$ there is an $i$-continuation. By
Lemma 5 for each such $i$, there is an edge $\sigma\in G(i)$ lying on
$\omega$. For any $i$ define an open set

$U_{i}=\cup_{\sigma\in G(i)}\Gamma_{\tilde{F}_{i}(\sigma_{2})}.$

Since $l(\tilde{F}_{i}(\sigma_{2}))>\sigma_{1}+i$ for $\sigma\in G(i)$,

$L(U_{i})\leq\sum\limits_{\sigma\in G(i)}2^{-\sigma_{1}-i}\leq 2^{-i},$

where $L$ is the uniform measure. Define $U^{\prime}_{i}=\cup_{j>i}U_{i}$,
$L(U^{\prime}_{i})\leq 2^{-i}$. We have proved that $\\{U^{\prime}_{i}\\}$ is
Martin-Löf test of randomness with respect to the uniform measure. Since for
any infinite $\omega$, $F(\omega)=\tilde{F}_{i}(\omega)$ for infinitely many
$i$, $F(\omega)\in\cap_{i}U^{\prime}_{i}$. Thus, the sequence $F(\omega)$ is
not Martin-Löf random with respect to the uniform measure $L$. $\Box$

###### Corollary 3

$\bar{P}$-almost every infinite sequence $\omega$ cannot be Turing equvalent
to a sequence which is Martin-Löf random with respect to some computable
measure. The a priory measure of all such sequences is positive.

Proof. The set of all computable sequences is countable. The continuity of the
semimeasure $P$ implies that $\bar{P}$-almost every sequence from its support
set is non-computable. By [26] (Theorem 3.1), each non-computable sequence
Martin-Löf random with respect to some computable measure is algorithmically
equivalent to a sequence which is Martin-Löf random with respect to the
uniform measure. Therefore, $\bar{P}$-almost every sequence $\omega$ from the
support set of the semimeasure $P$ cannot be Turing equvalent to a sequence
Martin-Löf random with respect to some computable measure.

Since the semimeasure $P$ is lower semicomputable, $cM\geq P$ for some
constant $c$. Then $\bar{M}(E_{P})\geq\bar{P}(E_{P})>0$. $\Box$

###  5.2 Infinitely divisible element

We will construct a non-zero infinitely divisible element ${\bf e}\in\Upsilon$
which does not contain any atom. In order to do this, we apply Template 1 with
specific recursive predicate $B(i,\sigma)$.

We will use the numbering of all pairs $\langle i,x\rangle$, where $i$ is a
number and $x$ is a finite sequence.888Recall that we identify finite sequence
and positive integer numbers. The inverse functions also exist: $[\langle
i,x\rangle]_{1}=i$ is a task number, and the sequence $[\langle
i,x\rangle]_{2}=x$ is a candidate for processing. Let $p(n)$ be such that for
any $i$, $p(n)=i$ for infinitely many $n$.

We say that a sequence $z$ of length $n$ is $i$-discarded by an edge
$\sigma\in G(i)$ at step $n$, where $i=[p(n)]_{1}$, if $l(z)=l(\sigma_{2})=n$
and $\tilde{F}_{i}(\sigma_{2})\subseteq z$. Let $D_{n}(\sigma)$ be the set of
sequences of length $n$ which are $i$-discarded by the extra edge $\sigma$.

We slightly modify Case 2 of Template 1 to avoid collision between new extra
edges drawn at any step $n$ and the sequences discarded at step $n$. Now, at
any step $n$, at most one extra edge $\sigma$ will be drawn in $G$, where
$\sigma_{1}\in C_{n}(i)$. Other elements of this set will be processed on
later steps one by one. This edge $\sigma$ defines the set $D_{n}(\sigma)$ of
$i$-discarded sequences of length $n$ such that
$D_{n}(\sigma)\cap\\{z:l(z)=n,\sigma_{1}\subseteq z\\}=\emptyset$.

We use the same sequence of all uniformly computable operators
$\\{\tilde{F}_{i}\\}$ as in Section 5.1.

Define the recursive predicate

$\displaystyle
B(i,\sigma)\Longleftrightarrow\tilde{F}_{i}(\sigma_{2})\not\subseteq\sigma_{2}\&\sum\limits_{z:z\in
D_{n}(\sigma)}R(z)\leq 2^{-(\sigma_{1}+3)},$ (18)

where $R$ denotes the frame of the $q$-flow constructed in $n-1$ steps and
$\tilde{F}_{i}$ is modified by (1).

Modification of Case 2.

Case 2. $w(i,n)<n$ and $C_{n}(i)\not=\emptyset$, where $i=[p(n)]_{1}$,
$C_{n}(i)$ is the set of all $x$ that requires processing, i.e., such that
$p(l(x))=i$, $w(i,n)\leq l(x)<n$, $s(x)>0$, $\beta(x,n)$ is defined and there
is no extra edge in $G^{n-1}$ outgoing from $x$ (processing step of the task
$i$).

If $x=[p(n)]_{2}\in C_{n}(i)$ then define

$\displaystyle G^{n}=G^{n-1}\cup\\{(x,\beta(x,n))\\}.$

and $q((x,\beta(x,n)))=s(x)$. If $s(x)<1$ then define $s(\beta(x,n))=0$ and
$s(y)=s(x)/(1-s(x))$ for all other $y$ of length $n$ such that $x\subset y$.
If $s(x)=1$ then define $s(y)=0$ for these $y$.

For any sequence $z$ of length $n$, which is $i$-discarded by the extra edge
$\sigma=(x,\beta(x,n))$, define $s(z)=1$.

Define $s(x)=0$ for all other $x$ of length $n$ and define
$q(\sigma)=\frac{1}{2}(1-s(\sigma_{1}))$ for all edges $\sigma$ of unit length
such that $l(\sigma_{1})=n$.

This modification does not change the basic properties of the Template 1.

Let $s$ be the flow delay function for the network $q$ and $P$ denotes the
$q$-flow. The frame $R$ is defined using equalities (9)–(10).

Similarly to how it was done in Section 5.4, we can prove that $P$ is
continuous lower semicomputable semimeasure.

We modify the proof of Lemma 7 for the case where some sequences are
discarded.

###### Lemma 8

$\bar{P}({\bf 1})>0$.

Proof. Let us estimate from below the value of $\bar{P}(\Omega)$. Consider

$S_{n}=\sum\limits_{u:l(u)=n}R(u)-\sum\limits_{\sigma:\sigma\in
G,l(\sigma_{2})=n}q(\sigma)R(\sigma_{1}).$

From the definition of the frame, we have

$\displaystyle\sum\limits_{u:l(u)=n+1}R(u)=\sum\limits_{u:l(u)=n}(1-s(u))R(u)+$
(19) $\displaystyle\sum\limits_{\sigma:\sigma\in
G,l(\sigma_{2})=n+1}q(\sigma)R(\sigma_{1}).$ (20)

In case $w(p(n),n)=n$

$\sum\limits_{u:l(u)=n}s(u)R(u)\leq\rho(n)=1/(n+3)^{2}.$

Combining this inequality with (19)–(20), where the sum (20) is equal to 0, we
obtain $S_{n+1}\geq S_{n}-1/(n+3)^{2}$.

Let $w(p(n),n)<n$ and $\sigma\in G$ such that $\sigma_{1}=[p(n)]_{2}$. Then

$\displaystyle\sum\limits_{u:l(u)=n}s(u)R(u)=$
$\displaystyle\sum\limits_{u:l(u)=n,u\not\in
D_{n}(\sigma)}s(u)R(u)+\sum\limits_{u:l(u)=n,u\in D_{n}(\sigma)}R(u).$ (21)

The first sum in (21) is bounded similarly as (16) of the proof of Lemma 7:

$\displaystyle\sum\limits_{u:l(u)=n,u\not\in D_{n}}s(u)R(u)\leq
q(\sigma)R(\sigma_{1}).$ (22)

The second sum is bounded as

$\displaystyle\sum\limits_{u:l(u)=n,u\in D_{n}(\sigma)}R(u)\leq
2^{-(\sigma_{1}+3)}.$ (23)

The bounds (22) and (23) implies the lower bound

$S_{n}\geq
1-\sum\limits_{i=1}^{\infty}1/(i+3)^{2}-\sum\limits_{\sigma}2^{-(\sigma_{2}+3)}\geq\frac{1}{2}$

for all $n$. Since $P\geq R$, we have

$\bar{P}(\Omega)=\inf\limits_{n}\sum\limits_{l(u)=n}P(u)\geq\inf\limits_{n}S_{n}\geq\frac{1}{2}.$

Lemma is proved. $\Box$

###### Lemma 9

Any two different infinite sequences $\omega$ and $\alpha$ from the set
$E_{P}$ are not Turing reducible to each other.

Proof. Assume that $\alpha=F_{i}(\omega)$ for some $i$. Since
$\omega\not=\alpha$, $\tilde{F}_{i}(\omega^{n})\not\subseteq\omega^{n}$ for
all sufficiently large $n$. Then by Lemma 5, for all sufficiently large
$n>w(i)$ such that $[p(n)]_{1}=i$ an edge $\sigma$ exists such that
$l(\sigma_{2})=n$, $\sigma_{2}\subset\omega$ and $B(i,\sigma)$ is satisfied,
in particular, $\sigma_{1}\in C_{n}(i)$. By construction $\sigma=[p(n)]_{2}$
for some of these $n$. Then the sequence $\alpha^{n}$ will be $i$-discarded
for some $n>w(i)$ and $s(\alpha^{n})=1$ will be defined. No extra edge
$\sigma^{\prime}$ such that
$\sigma^{\prime}_{1}\subset\alpha^{n}\subset\sigma^{\prime}_{2}$ can be drawn
at any step $n^{\prime}=l(\sigma^{\prime}_{2})>n$, and therefore, no extra
portion of the flow can go through the vertex $\alpha^{n}$. Indeed, any task
$j<i$ cannot draw extra edges on steps $n^{\prime}>n$ since $w(i,n)=w(i)$. At
the step $n$ the sessions of all tasks $j>i$ are terminated, and on the later
steps $n^{\prime}>n$ the tasks $j>i$ can draw only extra edges
$\sigma^{\prime}$ such that $l(\sigma^{\prime}_{1})>n$.

Hence, $q((\alpha^{n},\alpha^{n+1}))=0$, and so, $\alpha\not\in E_{P}$. This
contradiction proves that $\alpha$ is not Turing reducible to $\omega$. $\Box$

###### Theorem 3

There exists a non-zero infinitely divisible element ${\bf e}$ such that

${\bf e}\cap({\bf r}\cup{\bf c})={\bf 0}.$

Proof. Define ${\bf f}=[\bar{E}_{P}]$. Let ${\bf e}=i_{P}({\bf f})=[E]$.
Assume that ${\bf x}\subseteq{\bf e}$ and ${\bf x}\not={\bf 0}$. Take an
$X\in{\bf x}$ and put $X^{\prime}=X\cap E$. Clearly, $\bar{P}(X^{\prime})>0$.
Since $X^{\prime}\subseteq E$, by Lemma 1 $\bar{M}(X^{\prime})>0$. Since
$X^{\prime}\subseteq E_{P}$, by Lemma 9 any two sequences from $X^{\prime}$ do
not reducible to each other. Let us represent $X^{\prime}=X_{1}\cup X_{2}$,
where $X_{1}\cap X_{2}=\emptyset$, $\bar{P}(X_{1})>0$, and $\bar{P}(X_{2})>0$.
Let ${\bf x}_{1}=[\bar{X}_{1}]$ and ${\bf x}_{2}=[\bar{X}_{2}]$. Then ${\bf
x}={\bf x}_{1}\cup{\bf x}_{2}$, ${\bf x}_{1}\not={\bf 0}$, ${\bf
x}_{2}\not={\bf 0}$ and ${\bf x}_{1}\cap{\bf x}_{2}={\bf 0}$. Hence, $\bf x$
cannot be an atom. Theorem is proved. $\Box$

###  5.3 Template 2

In this section we present Template 2 which is a modification of Template 1
and which will be used to construct atoms of the algebra $\Upsilon$. The
modification given below does not affect the above properties of Template 1.

Let $p(n)$ and $\tilde{p}(n)$ be computable functions such that for each pair
of positive integer numbers $(i,k)$, $p(n)=i$ and $\tilde{p}(n)=k$ for
infinitely many $n$.

Any extra edge $\sigma$ corresponds to a task $i$, where
$p(l(\sigma_{1}))=p(l(\sigma_{2}))=i$. It also corresponds to some subtask
$(i,k)$, where $\tilde{p}(l(\sigma_{1}))=\tilde{p}(l(\sigma_{2}))=k$.

By induction on $n$, define a sequence of elementary networks. and the sets of
extra edges $G^{n}$.

Define $s(\lambda)=0$ and $G^{0}=\emptyset$. The induction hypothesis is the
same as for step $n$ of Template 1.

Consider an auxiliary function $w(i,n)$. The value of $w(i,n)$ is equal to the
least $m$ such that $m\leq n$, $p(m)=i$ and $m>l(\sigma_{2})$ for each extra
edge $\sigma$, which was drawn by a task $j<i$. In particular, for each
$n^{\prime}$ such that $w(i,n)\leq n^{\prime}\leq n$ no task $j<i$ was
processed. The formal definition was given by (14). We refer to $w(i,n)$ as to
the initial step of a session to process the task $i$.

The equality $w(i,n)=w(i,n-1)$ is violated (i.e. $w(i,n)\not=w(i,n-1)$) only
if some task $j<i$ has established an extra edge located above the level
$w(i,n-1)$, and thus it violates the condition (14) for the definition of
$w(i,n)$. Lemma 4 states that this can only happen at a finite number of
construction steps.

Define a family of equivalence relations between finite sequences depending on
the parameter $w$:

$x\sim_{w}y\Longleftrightarrow l(x)=l(y)\&\forall(w\leq i\leq
l(x)\Longrightarrow x_{i}=y_{i});$

Note that if $x\sim_{w}y$ then $x\sim_{w^{\prime}}y$ for each $w^{\prime}\geq
w$.

For any edges $\sigma$ and $\sigma^{\prime}$, define
$\sigma\sim_{w}\sigma^{\prime}$ if and only if
$\sigma_{1}\sim_{w}\sigma^{\prime}_{1}$ and
$\sigma_{2}\sim_{w}\sigma^{\prime}_{2}$.

Sometimes, we write $x\sim z$ instead of $x\sim_{w}z$, where
$w=w(p(l(x)),l(x))$.

During the construction process, we will execute the task $i$ by executing the
subtasks $(i,k)$ in the order of their priority. If the edge is drawn by
subtask $(i,k)$ then we say that it also is drawn by the task $i$.

At any step $n$, let $z_{i,1,n},\dots,z_{i,2^{w(i,n)},n}$ be all finite binary
sequences $z$ of length $w(i,n)$ written out in the lexicographic order. We
refer to the sets $T_{z_{i,t,n}}=\\{y:z_{i,t,n}\subseteq y\\}$ as to subtrees
of the tree $\Xi$ with the roots $z_{i,1,n},\dots,z_{i,2^{w(i,n)},n}$.

Given a set of extra edges $G$ let

$G(i)=\\{\sigma:\sigma\in G\&p(l(\sigma_{1}))=p(l(\sigma_{2}))=i\\}$

be the set of all extra edges drawn by the task $i$ and

$G(i,k)=\\{\sigma\in
G(i):\tilde{p}(l(\sigma_{1}))=\tilde{p}(l(\sigma_{2}))=k\\}$

be the subset of all extra edges drawn by the subtask $(i,k)$.

By definition, the $w(i,k,n)$ is equal to the smallest $m$ such that $m\leq n$
and the following conditions are satisfied. First, $p(m)=i$ and
$m>l(\sigma_{2})$ for each extra edge $\sigma$ which was drawn by the task
$j<i$. Second, $m>l(\sigma_{2})$ for each extra edge $\sigma$ that was drawn
by some subtask $(i,t)$, where $t<k$. This means that at all steps
$n^{\prime}$ such that $w(i,k,n)\leq n^{\prime}\leq n$ any subtask $(j,t)$,
where $j<i$ or $j=i$ and $t<k$, did not draw new extra edges.

Let us give the exact definition. For $k\leq 2^{w(i,n)}$ define

$\displaystyle w(i,k,n)=\min\\{m:m\leq n\&p(m)=i\&\tilde{p}(m)=k\&$
$\displaystyle\forall j\forall\sigma((j<i\&\sigma\in G^{n-1}(j)\rightarrow
m>l(\sigma_{2}))\&$ (24) $\displaystyle\forall t\forall\sigma(1\leq
t<k\&\sigma\in G^{n-1}(i,t)\rightarrow m>l(\sigma_{2}))\\}.$

Assume that $\min\emptyset=\infty$.

We say that $w(i,k,n)$ is the initial step of the sub-session for executing
the subtask $(i,k)$. By definition, $w(i,k,n)\geq w(i,n)$ for each $i$ and
$k$. Any session for the execution of any task $i$ consists of sub-sessions
$(i,k)$, which are executed in order of their priority.

Violation of the equality $w(i,k,n)=w(i,k,n-1)$ can occur because
$w(i,n)\not=w(i,n-1)$ or for $w(i,n)=w(i,n-1)$ because some subtask $(i,t)$,
where $t<k$, draws an extra edge above the level $w(i,k,n-1)$ and thus
violates the condition for the definition of $w(i,k,n-1)$. It will be shown
below that such a violation will occur at no more than a finite number of
steps $n$ such that $w(i,n)=w(i,n-1)$.

We define a network, depending on a recursive predicate $B(i,\sigma)$, where
$i$ is a positive integer number (task number), $\sigma$ is an extra edge.

The goal of the task $i$ is the same as for Template 1 – to draw extra edges
$\sigma$ such that each infinite sequence $\omega$ from the support set of the
corresponding network flow passes through one of these edges. Each such edge
$\sigma$ should satisfy the predicate $B(i,\sigma)$.

There is an additional requirement. In order for the corresponding flow to
define an atom of the algebra $\Upsilon$, in the modified construction the
value of the flow through any two edges $\sigma$ and $\sigma^{\prime}$ such
that $\sigma^{\prime}\sim\sigma$ should be the same. Therefore, when the edge
$\sigma$ is drawn by the task $i$, all the edges $\sigma^{\prime}\sim\sigma$
and $\sigma^{\prime}\not=\sigma$ become dependent on it. All assignments on
these edges should to mimic the assignments on $\sigma$. In this case, a
collision may occur if we try to simultaneously make assignments of the task
$i$ by Case 2 for another edge, which is located in a different subtree. In
order to avoid a collision when setting the edges of the task $i$, at step $n$
we split the process of executing the task $i$ into subtasks $(i,k)$, where
$k=1,\dots 2^{w(i,n)}$.

At any step $n$ of the construction we execute the subtask $(i,k)$ into the
subtree $T_{z_{i,k,n}}$ (we call it the leading subtree), where
$k=\tilde{p}(n)$, and duplicate all actions in all other subtrees
$T_{z_{i,t,n}}$ for $t\not=k$ (we call them dependent subtrees). We will
perform the task $i$ for the other subtrees in subsequent steps in order of
their priority, still repeating all the assignments in the remaining subtrees.

By the construction below if the subtask $(i,k)$ is executed at step $n$, then
for each extra edge $\sigma$ which was drawn by any subtask $(i,t)$ where
$t<k$ it will be $l(\sigma_{2})<w(i,k,n)$ and, therefore, the equality
$w(i,t,n)=w(i,t,n-1)$ will not be violated for $t<k$. If a new edge will be
drawn in this subtree then all subtasks $(i,t)$ corresponding to subtrees with
lower priority $t>k$ will be terminated and the equalities
$w(i,t,n)=w(i,t,n-1)$ will be violated. These subtasks should be reinstalled
on later steps.

Each extra edge $\sigma$ will refer to a task $i$ such that
$p(l(\sigma_{1}))=p(l(\sigma_{2}))=i$ and to the subtask $(i,k)$, where
$\tilde{p}(l(\sigma_{1}))=\tilde{p}(l(\sigma_{2}))=k$.

The predicate $B$ defines the function of setting an extra edge

$\beta(x,n)=\min\\{y:l(y)=n,p(l(y))=p(l(x)),B(p(l(x)),(x,y))\\}.$

We assume that $\min\emptyset$ is undefined.

Define $s(\lambda)=0$ and $G^{0}=\emptyset$.

At any step $n$, let $i=p(n)$ and $k=\tilde{p}(n)$.

Let $n\geq 1$ and $G^{n-1}$ and $q(\sigma)$ be defined for every $\sigma\in
G^{n-1}$, $s(x)$ be defined for every $x$ such that $l(x)\leq n-1$, and
$s(x)=s(x^{\prime})$ for every $x$ and $x^{\prime}$ of length $<n$ such that
$x\sim_{w(i,n)}x^{\prime}$. Let also, $q(\sigma)=\frac{1}{2}(1-s(\sigma_{1})$
for each $\sigma$ of unit length such that $l(\sigma_{2})=n$.

If $k>2^{w(i,n}$ then define $s(x)=0$ for each $x$ of length $n$ and
$G^{n}=G^{n-1}$ and go to the next step. If $k\leq 2^{w(i,n)}$ then go to the
definitions below.

The construction of any step $n$ splits into three cases:

Case 1. $w(i,k,n)=n$ (starting a new sub-session for executing the subtask
$(i,k)$, where $i=p(n)$ and $k=\tilde{p}(n)$: first installing or reinstalling
of the subtask $(i,k)$).

Define $s(y)=1/\rho(n)$ for all $y$ such that $l(y)=n$ and set
$G^{n}=G^{n-1}$, where $\rho(n)=(n+3)^{2}$.

Case 2. $w(i,k,n)<n$ and $C_{n}(i,k)\not=\emptyset$, where $C_{n}(i,k)$
denotes the set of all sequences $x$ which should be processed by subtask
$(i,k)$, i.e., such that $z_{i,k,n}\subseteq x$, $p(l(x))=i$ and
$\tilde{p}(l(x))=k$, $w(i,k,n)\leq l(x)<n$, $s(x)>0$, $\beta(x,n))$ is defined
and there is no extra edge from $G^{n-1}$ outgoing from $x$ (the subtask
$(i,k)$ processing step).

In this case, we make identical assignments in all subtrees $T_{z_{i,t,n}}$,
$1\leq t\leq 2^{w(i,n)}$, which repeat the assignments in the leading subtree
$T_{z_{i,k,n}}$ of the subtask $(i,k)$:

1) For any $x\in C_{n}(i,k)$ define $s(z)=0$ for each $z$ such that
$z\sim_{w(i,n)}\beta(x,n)$ and $q(\sigma)=s(x)$ for every $\sigma$ such that
$\sigma\sim_{w(i,n)}(x,\beta(x,n))$. We add all these edges $\sigma$ to
$G^{n-1}$ and get $G^{n}$.

2) If $s(x)<1$ then for any $y$ such that $x\subset y$, $l(y)=n$ and
$y\not=\beta(x,n)$ define $s(z)=s(x)/(1-s(x))$ for each $z$ such that
$z\sim_{w(i,n)}y$.

3) If $s(x)=1$ then define $s(z)=0$ for all these $z$.

4) Define $s(z)=0$ for all other $z$ of length $n$.

Case 3. Cases 1 and 2 do not occure. In this case define $s(x)=0$ for each $x$
of length $n$, and define $G^{n}=G^{n-1}$.

After all, define $q(\sigma)=\frac{1}{2}(1-s(\sigma_{1}))$ for each $\sigma$
of unit length such that $l(\sigma_{1})=n$.

This concludes the description of the induction step.

Define $G=\cup_{n}G^{n}$ and $G(i)=\cup_{n}G^{n}(i)$,
$G(i,k)=\cup_{n}G^{n}(i,k)$ for any $i$ and $k$. Let
$w(i)=\lim_{n\to\infty}w(i,n)$ and $w(i,k)=\lim_{n\to\infty}w(i,k,n)$.

The analogs of the Lemmas 2–4 also take place for the modified construction.
In particular, any task $i$ is processed only at a finite number of steps and
the set $G(i)$ is finite and $w(i)<\infty$ for all $i$.

The next lemma states that any subtask $(i,k)$ is processed only at a finite
number of steps.

###### Lemma 10

The set $G(i,k)$ is finite and $w(i,k)<\infty$ for all $i$ and $k\leq
2^{w(i)}$.

Proof. By Lemma 4 $w(i)<\infty$. Then $w(i,n)=w(i)$ for all $n\geq n^{\prime}$
for some $n^{\prime}$. Further, following the proof of Lemma 4, where the
function $w(i,n)$ is replaced with $w(i,k,n)$, we show that
$w(i,k,n)\not=w(i,k,n-1)$ only for a finite number of different $n\geq
n^{\prime}$. $\Box$

The following duplication property takes place.

###### Lemma 11

For any $i$, $q(\sigma)=q(\delta)$ for each $\sigma,\delta\in G$ such that
$\sigma\sim_{w(i)}\delta$.

Proof. Since $w(i)=\lim_{n\to\infty}w(i,n)$, only tasks $j\geq i$ can draw the
extra edges $\sigma\in G$ on steps $n\geq w(i)$, where $l(\sigma_{1})\geq
w(i)$. Assume that the extra edges $\sigma,\delta$ be drawn by some subtask
$(j,k)$, where $j\geq i$. By definition a single extra edge
$\sigma^{\prime}\in G$ exists in the leading subtree such that
$z_{j,k,n}\subset\sigma^{\prime}$, $\sigma\sim_{w(j,n)}\sigma^{\prime}$ and
$q(\sigma)=q(\sigma^{\prime})$, where $n=l(\sigma_{2}$ and $j=p(n)$ and
$k=\tilde{p}(n)$. Similarly, a single extra edge $\delta^{\prime}\in G$ exists
such that $\delta\sim_{w(j,n)}\delta^{\prime}$ and
$q(\delta)=q(\delta^{\prime})$.

Since $\sigma\sim_{w(i)}\delta$ and $w(j,n)\geq w(i)$, we have
$\sigma\sim_{w(j,n)}\delta$. Then $\sigma^{\prime}=\delta^{\prime}$ and by the
construction $q(\sigma)=q(\delta)$. $\Box$

Let $R$ be the frame of the $q$-flow $P$. Clearly, the semimeasure $P$ is
lower semicomputable.

By Lemma 6 the semimeasure $P$ is continuous, since for any $i$ the number
$w(i)$ separates $G$.

The support set of a semimeasure $P$ is equal to

$E_{P}=\\{\omega\in\Omega:\forall n(P(\omega^{n})\not=0)\\}.$

The following lemma will enable us to apply Kolmogorov 0 or 1 law to the
measure $\bar{P}$, where $P$ is the $q$-flow. Although this measure is not
normalized, this does not lead to a loss of generality, since the subsequent
statements do not depend on the multiplicative factor.

For any $i$, let $f_{i}(\omega)=\omega_{i}$ be a random variable in the
probability space $(\Omega,\bar{P})$.

###### Lemma 12

For any $n>w(i)$, the random variable $f_{n}$ does not depend on the random
variables $\\{f_{j}:j\leq w(i)\\}$.

Proof. Since $w(i)=\lim_{n\to\infty}w(i,n)$, only tasks $i^{\prime}\geq i$ can
draw the extra edges $\sigma\in G$ on steps $n\geq w(i)$, where
$l(\sigma_{1})\geq w(i)$. From this it follows that for $l(v)>w(i)$, the
formula (10) can be rewritten as

$\displaystyle R(v)=\sum\limits_{l(\sigma_{1})\geq
w(i),\sigma_{2}=v}q(\sigma)R(\sigma_{1}).$ (25)

Assume that $v\sim_{w(i)}v^{\prime}$ and $l(v)>w(i)$. These sequences belong
to some subtrees. By Lemma 11 for any $\sigma\in G$ such that
$l(\sigma_{1})\geq w(i)$ and $\sigma_{2}=v$ there exists $\sigma^{\prime}\in
G$ which belongs to the same subtree as $v^{\prime}$ and such that
$\sigma^{\prime}\sim_{w(i)}\sigma$ and $q(\sigma^{\prime})=q(\sigma)$.
Clearly, $\sigma^{\prime}_{2}=v^{\prime}$. Using induction on recursive
definition (25), we obtain

$R(v)/R(v^{w(i)})=R(v^{\prime})/R(v^{\prime w(i)}).$ (26)

Since there are no extra edges $\sigma$ such that $\sigma_{1}\subset
z^{w(i)}\subset\sigma_{2}$, the equality $P(z^{w(i)})=R(z^{w(i)})$ takes
place. Now, using the representation (11)–(12), we will prove the similar
equality for $P$.

Let $l(y)>w(i)$ and $y\sim_{w(i)}z$. Then $y\sim_{n}z$ for each $n\geq w(i)$.
By Lemma 11 for each extra edge $\sigma\in G$ such that
$y\subseteq\sigma_{1}\subset y\subseteq\sigma_{2}$, an extra edge
$\sigma^{\prime}\sim_{w(i)}\sigma$ exists such that
$z\subseteq\sigma^{\prime}_{1}\subseteq z\subseteq\sigma^{\prime}_{2}$ and
$q(\sigma)=q(\sigma^{\prime})$. From these and by (26), we obtain

$P(y)/P(y^{w(i)})=P(z)/P(z^{w(i)})$ (27)

for all $y$ and $z$ such that $y\sim_{w(i)}z$. From this we obtain

$\bar{P}(y)/\bar{P}(y^{w(i)})=\bar{P}(z)/\bar{P}(z^{w(i)})$

for all $y$ end $z$ such that $y\sim_{w(i)}z$.

Therefore, the conditional probability

$\bar{P}(y|x)=\frac{\bar{P}(xy)}{\bar{P}(x)}$

does not depend on the choice of the initial fragment $x$ of the sequence $y$
for $l(x)=w(i)$ and $l(y)>w(i)$:

In particular, the random variables $f_{j}(\omega)=\omega_{j}$ do not depend
on the random variables $f_{s}(\omega)=\omega_{s}$ for $s\leq w(i)<j$. $\Box$

We define an atom consisting of nonstochastic Turing degrees.

Let $q$ be the network defined using the Template 2, $G$ be the set of all
extra edges, and $s$ be the corresponding flow delay function.

The following lemma is a corollary of Lemma 12.

###### Lemma 13

For any $A\subseteq\Omega$ containing, together with each sequence, all
sequences differing from it by a finite number of bits, $\bar{P}(A)=0$ or
$\bar{P}(A)=\bar{P}(\Omega)$.

Proof.999A specific for Cantor space $(\Omega,L)$ proof of this lemma see in
Downey and Hirschfeldt [3], Theorem 1.2.4. See also, Holzl and Porter [4],
Theorem 4.9. To apply the Kolmogorov 0 or 1 law, consider the independent
random variables $\tilde{f}_{1},\tilde{f}_{2},\dots$, where

$\tilde{f}_{i}(\omega)=f_{w(i)+1}(\omega)\dots
f_{w(i+1)}(\omega)=\omega_{w(i)+1}\dots\omega_{w(i+1)}$

and $f_{i}(\omega)=\omega_{i}$. Clearly, the random variables
$\tilde{f}_{1}(\omega),\tilde{f}_{2}(\omega),\dots$ generate the same
$\sigma$-algebra as the random variables $f_{1}(\omega),f_{2}(\omega),\dots$.

The set $A$ satisfying the condition of the lemma lies in the $\sigma$-algebra
generated by the set of independent random variables
$\tilde{f}_{k},\tilde{f}_{k+1},\dots$ for each $k$, and therefore, it lies in
the residual $\sigma$-algebra of the entire sequence
$\tilde{f}_{1},\tilde{f}_{2},\dots$. By Kolmogorov 0 or 1 law $\bar{P}(A)=0$
or $\bar{P}(A)=\bar{P}(\Omega)$. $\Box$

###### Corollary 4

There exists an atom of $\Upsilon$.

Proof. Let ${\bf p}=[\bar{E}_{P}]$. By Lemma 7 $P({\bf p})>0$, then ${\bf
p}\not={\bf 0}$. Define ${\bf d}=i_{P}({\bf p})$. By definition
$\bar{P}(i_{P}({\bf p}))=\bar{P}({\bf d})$. Then ${\bf d}\not={\bf 0}$.

Assume that ${\bf d}={\bf a}\cup{\bf b}$, where ${\bf a}\not={\bf 0}$, ${\bf
b}\not={\bf 0}$ and ${\bf a}\cap\bf b={\bf 0}$. By Corollary 1 $\bar{P}({\bf
a})>0$ and $\bar{P}({\bf b})>0$, that contradicts Lemma 13. This contradiction
proves that ${\bf d}$ is an atom. $\Box$

###  5.4 Atom of nonstochastic Turing degrees

Corollary 4 shows that the network flow defined by Template 2 generate an atom
regardless what predicate $B(i,\sigma)$ is used. Specifying this predicate, we
obtain the following theorem.

###### Theorem 4

There exists an atom ${\bf d}$ such that ${\bf d}\cap({\bf c}\cup{\bf r})={\bf
0}$.

Proof. Let us specify the predicate:

$\displaystyle B(i,\sigma)\Longleftrightarrow
l(\tilde{F}_{i}(\sigma_{2}))>\sigma_{1}+i,$

where the finite sequence $\sigma_{1}$ (the starting point of the edge
$\sigma$) is identified with its order number in the natural numbering of the
set $\Xi$.

The following statements are similar to Theorem 2 and Corollary 3 and their
proofs are the same:

1) For any infinite sequence $\omega$ from the support set of the semimeasure
$P$ and for any computable operator $F$, if $F(\omega)$ is infinite, then the
sequence $F(\omega)$ is not Martin-Löf random with respect to the uniform
measure.

2) $\bar{P}$-almost every infinite sequence $\omega$ is not Martin-Löf random
with respect to any computable measure.

From these statements ${\bf d}\cap({\bf c}\cup{\bf r})={\bf 0}$ follows.
$\Box$

###  5.5 Decomposition into countable sequence of atoms

We will construct an infinite sequence of lower semicomputable semimeasures
$P_{1},P_{2},\dots$ which will define a sequence of pairwise different atoms
$\bf d_{1},\bf d_{2},\dots$.

We use the same sequence of all computable operators $\\{F_{i}\\}$ and their
modified versions $\\{\tilde{F}_{i}\\}$ as in Section 5.1.

Let $\langle x_{1},x_{2},x_{3}\rangle$ be the number of a triple of natural
numbers, for some fixed computable one-to-one correspondence between all
triples $\langle x_{1},x_{2},x_{3}\rangle$ such that $x_{1}\not=x_{2}$, and
all positive integer numbers.

The inverse functions $[\langle x_{1},x_{2},x_{3}\rangle]_{t}=x_{t}$,
$t=1,2,3$, are also given. The order number $i=\langle
x_{1},x_{2},x_{3}\rangle$ of each such triplet will be a code of some task
$i$, where $x_{1}$ is the number of the computable operator, $x_{2}$ is called
task base, $x_{3}$ is task target. By the main property of triplets numbering,
any number $m$ cannot be both the target and the base of the same task.

Let us define the networks $q_{m}$ for $m=1,2,\dots$. We will execute the
tasks what are common to all networks $q_{m}$. At any step $n$ the task
$i=p(n)$ will execute Template 2 for the network $q_{[i]_{1}}$, which is the
base of the task $i$ and discard some vertices of the network $q_{[i]_{2}}$,
which is the target of the task $i$. All other networks remains unchanged at
the step $n$. One and the same network can serve as a base for some task at
some steps and as a target at other steps, but not at the same time.

For any $m$, let $G^{n}_{m}(i)$ be the set of all extra edges drawn by a task
$i$ for a network $q_{m}$ at steps $\leq n$, $G^{n}_{m}=\cup_{i}G^{n}_{m}(i)$.
Since at any step of the construction only a finite number of extra edges can
be drawn, for any $n$, $G^{n}_{m}=\emptyset$ for almost all $m$.

Definition (14) of the function $w(i,n)$ is changed to

$\displaystyle w(i,n)=\min\\{n^{\prime}:n^{\prime}\leq n\&p(n^{\prime})=i\&$
$\displaystyle\forall m\forall j\forall\sigma((j<i\&\sigma\in
G_{m}^{n-1}(j)\rightarrow n^{\prime}>l(\sigma_{2})).$

and the definition (5.3) of the function $w(i,k,n)$ is changed to

$\displaystyle w(i,k,n)=\min\\{n^{\prime}:n^{\prime}\leq
n\&p(n^{\prime})=i\&\tilde{p}(n^{\prime})=k\&$ $\displaystyle\forall m\forall
j\forall\sigma((j<i\&\sigma\in G_{m}^{n-1}(j)\rightarrow
n^{\prime}>l(\sigma_{2}))\&$ $\displaystyle\forall m\forall
t\forall\sigma(1\leq t<k\&\sigma\in G_{m}^{n-1}(i,t)\rightarrow
n^{\prime}>l(\sigma_{2}))\\}.$

We add a new element to construction of Template 2. We say that a finite
sequence $x$ of length $n$ is $i$-discarded by a sequence $y$ (or by an edge
$\sigma\in G^{n}_{[i]_{1}}$ such that $\sigma_{2}=y$), if $l(y)=l(x)$ and a
finite sequence $u$ exist such that $x\sim_{w(i,n)}u$ and
$\tilde{F}_{[i]_{3}}(y)\subseteq u$.

We can now define the recursive predicate which is needed to specify Template
2.

$B(i,\sigma)\Longleftrightarrow\sum\limits_{z}R_{[i]_{2}}(z)\leq
2^{-(\sigma_{1}+3)},$ (28)

where $R_{[i]_{2}}$ denotes the frame of the flow through the elementary
network $q_{[i]_{2}}$, and the sum is taken over all $z$ of length
$l(\sigma_{2})$, which are $i$-discarded by an extra edge $\sigma\in
G^{n}_{[i]_{1}}(i)$. Here in the exponent degree we identify the finite
sequence $\sigma_{2}$ and its order number.

Any task $i$ relates to the two networks: to its base $q_{[i]_{1}}$ and to its
target $q_{[i]_{2}}$. The goal of the task $i=\langle
x_{1},x_{2},x_{3}\rangle$ is to provide conditions under which the operator
$F_{x_{3}}$ could not transform any infinite sequence from the support set of
the semimeasure $P_{x_{1}}$ to a sequence from the support set of the
semimeasure $P_{x_{2}}$. A competing requirement is that these semimeasures
should be nontrivial, i.e. there should be $\bar{P}_{x_{1}}(\Omega)>0$ and
$\bar{P}_{x_{2}}(\Omega)>0$.

Construction of the networks $q_{m}$.

We define the networks $q_{m}$ for $m=1,2,\dots$ using mathematical induction
on steps $n=1,2,\dots$.

Define $s_{m}(\lambda)=0$ and $G_{m}^{0}=\emptyset$ for all $m$.

Let $n\geq 1$ and for every $m$, the sets $G_{m}^{n-1}$ and the values
$q_{m}(\sigma)$ be defined for all $\sigma\in G^{n-1}_{m}$, $s_{m}(x)$ be
defined for all $x$ such that $l(x)\leq n-1$ and
$q_{m}(\sigma)=\frac{1}{2}(1-s_{m}(\sigma_{1})$ for each $\sigma$ of unit
length such that $l(\sigma_{2})=n$.

At any step $n$ of induction execute the task $i=p(n)$:

1) denote $m=[i]_{1}$ and execute step $n$ of Template 2 with the predicate
(28), where $s$, $q$ and $G^{n}$ are replaced with $s_{m}$, $q_{m}$ and
$G^{n}_{m}$;

2) denote $m^{\prime}=[i]_{2}$ and define
$G^{n}_{m^{\prime}}=G^{n-1}_{m^{\prime}}$ and $s_{m^{\prime}}(x)=1$ for each
$x$ of length $n$, which is $i$-discarded at step $n$ by some edge $\sigma\in
G^{n}_{m}(i)$ such that $l(\sigma_{2})=n$ and define $s_{m^{\prime}}(x)=0$ for
all other $x$, $l(x)=n$;

3) for any $m\not=[i]_{1}$ and $m\not=[i]_{2}$ define $G^{n}_{m}=G^{n-1}_{m}$
and $s_{m}(x)=0$ for each $x$ such that $l(x)=n$;

4) After all, define $q_{m}(\sigma)=\frac{1}{2}(1-s_{m}(\sigma_{1}))$ for each
$m$ and for each $\sigma$ of unit length such that $l(\sigma_{1})=n$.

This concludes the description of the induction step.

By Lemma 11 $q_{m}(\sigma)=q_{m}(\sigma^{\prime})$ for any
$\sigma,\sigma^{\prime}\in G_{m}$ such that $\sigma\sim\sigma^{\prime}$.

Let $P_{m}$ be the $q_{m}$-flow.

By Lemma 6 the semimeasure $P_{m}$ is continuous for each $m$, since the
number $w(i)$ separates $G_{m}$ for each $i$.

The support set of any semimeasure $P_{m}$ is equal to

$E_{P_{m}}=\\{\omega\in\Omega:\forall n(P_{m}(\omega^{n})\not=0)\\}.$

The following lemma is similar to Lemma 7 but its proof has some new details.

###### Lemma 14

$\bar{P}_{m}({\bf 1})>0$ for each $m$.

Proof. Let us estimate from below the value of $\bar{P}_{m}(\Omega)$. Let
$R_{m}$ be the frame of the network $q_{m}$. Define

$S_{m,n}=\sum\limits_{u:l(u)=n}R_{m}(u)-\sum\limits_{\sigma:\sigma\in
G_{m},l(\sigma_{2})=n}q_{m}(\sigma)R_{m}(\sigma_{1}).$

By definition of the flow delay function,

$\displaystyle\sum\limits_{u:l(u)=n+1}R_{m}(u)=\sum\limits_{u:l(u)=n}(1-s_{m}(u))R_{m}(u)+$
(29) $\displaystyle\sum\limits_{\sigma:\sigma\in
G_{m},l(\sigma_{2})=n+1}q_{m}(\sigma)R_{m}(\sigma_{1}).$ (30)

Let $m$ be a base of the task $p(n)$ at step $n$, i.e., $m=[p(n)]_{1}$.

Let us first consider the case $w(p(n),n)<n$. In this case the proof of this
lemma coincides with the corresponding part of the proof of Lemma 7, where the
delay function $s$ is replaced with the delay function $s_{m}$. We pass this
part of the proof and obtain $S_{m,n+1}\geq S_{m,n}$.

Consider the case $w(p(n),n)=n$. As in the proof of Lemma 7
$\sum\limits_{u:l(u)=n}R_{m}(u)\leq 1$ and

$\sum\limits_{u:l(u)=n}s_{m}(u)R_{m}(u)\leq\rho(n)=1/(n+3)^{2}.$

Combining this inequality with (29)–(30), we obtain $S_{m,n+1}\geq
S_{m,n-1}/(n+3)^{2}$.

Let $m$ be a target of the task $p(n)$ on step $n$, i.e., $m=[p(n)]_{2}$. Then

$\displaystyle\sum\limits_{l(u)=n}s_{m}(u)R_{m}(u)=\sum\limits_{u\in
D}R_{m}(u)\leq\sum\limits_{\sigma\in
G_{m},l(\sigma_{2})=n}2^{-(\sigma_{1}+3)},$ (31)

where $D$ is the set of all $u$ of length $n$, which are $p(n)$-discarded by
sequences $\sigma_{2}$, where $\sigma\in G_{[p(n)]_{1}}$ and
$l(\sigma_{2})=n$.

Recall that in the exponent, we identify the finite sequence $\sigma_{1}$ and
its order number. Therefore,

$S_{m,n+1}\geq S_{m,n}-\sum\limits_{\sigma\in
G_{[p(n)]_{1}},l(\sigma_{2})=n}2^{-(\sigma_{1}+3)}.$

If $m$ is neither base no target of the task $p(n)$ at step $n$ (i.e.
$[p(n)]_{1}\not=m$ and $[p(n)]_{2}\not=m$), then $s_{m}(u)=0$ for each $u$ of
length $n$ and there is no edge $\sigma\in G_{m}$, such that
$l(\sigma_{2})=n$. Hence, $S_{m,n+1}=S_{m,n}$.

Using these bounds for $S_{m,n}$ and $S_{m,0}=1$, we obtain

$S_{m,n}\geq
1-\sum\limits_{i=1}^{\infty}(i+3)^{-2}-\sum\limits_{x\in\Xi}2^{-(x+3)}\geq\frac{1}{2}$

for all $n$. Since $P_{m}\geq R_{m}$, we have

$\bar{P}_{m}(\Omega)=\inf\limits_{n}\sum\limits_{l(u)=n}P_{m}(u)\geq\inf\limits_{n}S_{m,n}\geq\frac{1}{2}.$

Lemma is proved. $\Box$

###### Lemma 15

If $k\not=m$ then $F_{t}(E_{P_{k}})\cap E_{P_{m}}=\emptyset$ for all $t$.

Proof. Assume that an $\omega\in E_{k}$ exists such that $F_{t}(\omega)\in
E_{m}$ for some $t$. Consider the task $i=\langle k,m,t\rangle$. For any $n$,
let $D_{n}$ be the set of all $z$ of length $n$ that are $i$-discarded by the
finite sequence $\omega^{n}$. It follows from continuity of $P_{m}$ that

$\lim\limits_{n\to\infty}\sum\limits_{z\in
D_{n}}P_{m}(z)\leq\lim\limits_{n\to\infty}2^{w(i,n)}P_{m}(\tilde{F}_{t}(\omega^{n}))=0.$

Besides, $P_{k}(\omega^{n})\not=0$ for all $n$. From here it is easy to see
that for each $n$ the sequence $\omega^{n}$ has an $i$-extension ($\omega$
itself is suitable as such extension).

By Lemma 5 an edge $\sigma\in G_{k}(i)$ will be drawn on some step $n>w(i)$
such that $l(\sigma_{2})=n$, $\sigma_{2}\subset\omega$ and the sequence
$(\tilde{F}_{t}(\omega))^{n}$ is $i$-discarded by the sequence $\sigma_{2}$.
Since $w(i,n)=w(i)$, no extra edge $\sigma^{\prime}$ such that
$\sigma^{\prime}_{1}\subset(\tilde{F}_{t}(\omega))^{n}\subset\sigma^{\prime}_{2}$
can be drawn at a step $n^{\prime}=l(\sigma^{\prime}_{2})>n$, and therefore,
no extra portion of the flow can go through the vertex
$(\tilde{F}_{t}(\omega))^{n}$. Then
$q_{m}(\big{(}(\tilde{F}_{t}(\omega))^{n},(\tilde{F}_{t}(\omega))^{n+1})\big{)}=0$
that implies $F_{t}(\omega)\not\in E_{m}$. The resulting contradiction proves
the lemma. $\Box$

###### Theorem 5

The set of all atoms of $\Upsilon$ is countable.

Proof. Let ${\bf p}_{m}=[\bar{E}_{P_{m}}]$. By Lemma 14 $P_{m}({\bf
p}_{m})>0$, then ${\bf p}_{m}\not={\bf 0}$. By Lemma 15 for $k\not=m$, any
$\alpha\in E_{P_{k}}$ and $\beta\in E_{P_{m}}$ do not reduce to each other.
Therefore, ${\bf p}_{k}\cap{\bf p}_{m}={\bf 0}$. Define ${\bf
d}_{m}=i_{P_{m}}({\bf p}_{m}))$. Since $\bar{P}_{m}(i_{P_{m}}({\bf
p_{m}}))=\bar{P}_{m}({\bf p_{m}})$, we have ${\bf d}_{m}\not={\bf 0}$. From
${\bf d}_{m}\subseteq{\bf p}_{m}$ the equality ${\bf d}_{k}\cap{\bf
d}_{m}={\bf 0}$ follows for $k\not=m$.

Assume that ${\bf d}_{m}={\bf a}\cup{\bf b}$, where ${\bf a}\not={\bf 0}$,
${\bf b}\not={\bf 0}$ and ${\bf a}\cap\bf b={\bf 0}$. Then by Corollary 1
$\bar{P}_{m}({\bf a})>0$ and $\bar{P}_{m}({\bf b})>0$, which contradicts
Corollary 13. This contradiction proves that ${\bf d}_{m}$ is an atom for each
$m$. Theorem is proved. $\Box$

Theorems 3 and 5 imply the main result of this paper on decomposition of the
maximal element of LV-algebra.

###### Theorem 6

It holds ${\bf 1}=\cup_{i=1}^{\infty}{\bf a}_{i}\cup{\bf d}$, where ${\bf
a}_{1},{\bf a}_{2},\dots$ is the infinite sequence of all atoms and ${\bf d}$
is the non-zero infinitely divisible element.

###  5.6 Decomposition of the hyperimmune LV-degree into atoms

Let $\bf h$ be the element of $\Upsilon$ defined by the collection of all
hyperimmune sequences. We call this element hyperimmune LV-degree. Rumyantsev
and Shen [13] proved that hyperimmune sequences can be generated by some
probabilistic machine with positive probability. From this ${\bf h}\not={\bf
0}$ follows. In this section we present a decomposition of $\bf h$ into a
union of the infinite sequence of atoms and of the infinitely divisible
element.

An infinite subset $A\subseteq\cal N$ is called hyperimmune if there is no
computable function $f$ such that $f(i)\geq z_{i}$ for every $i$, where
$z_{1}<z_{2}<\dots$ be all elements of the set $A$ arranged in ascending
order. Let $a=a_{1}a_{2}\dots$ be the characteristic (binary) sequence of the
set $A$, i.e., $a_{i}=1$ if and only if $i\in A$ for every $i$. We call $a$
hyperimmune sequence. We will study LV-degrees generated by Turing degrees of
hyperimmune sequences.

An infinite binary sequence $\alpha$ is called sparse if it contains
infinitely many ones and there is no computable total function $f$ such that
for each $k$ the prefix of $\alpha$ of length $f(k)$ contains at least $k$
ones.

###### Proposition 1

A set $A$ is hyperimmune if and only if its characteristic sequence is sparse.

Proof. Assume that a set $A$ is not hyperimmune. Then $f(i)\geq z_{i}$, where
$z_{1}<z_{2}<\dots$ be all elements of the set $A$ arranged in ascending
order. It holds $a_{z_{i}}=1$ for all $i$ and $a_{j}=0$ for each $j\not\in A$.
Since $a_{z_{i}}=1$ for each $i$, the prefix of $a$ of length $f(i)$ contains
at least $i$ ones for each $i$, i.e., the sequence $a$ is not sparse.

On other side, assume that the characteristic sequence $a$ of the set $A$ is
not sparse. Then there is a computable function $f$ such that for each $k$ the
prefix of $a$ of length $f(k)$ contains at least $k$ ones. Since $a_{z_{i}}=1$
for each $i$, $f(k)\geq z_{k}$, i.e., the set $A$ is not hyperimmune. $\Box$

More information about the hyperimmune LV-degrees can be found in Holzl and
Porter [4], Proposition 4.15.

The following theorems 7, 8, and 9 present a decomposition of the hyperimmune
degree into the union of a countable sequence of atoms and a non-zero
infinitely divisible element.

###### Theorem 7

There exists an infinite sequence ${\bf h}_{1},{\bf h}_{2},\dots$ of atoms
defined by collections of hyperimmune sequences.

Proof. We modify Template 2 for the case of two recursive predicates
$B_{1}(j,\sigma)$ and $B_{2}(j,\sigma)$.

We call $i=p(l(x))$ the atoms difference task if $i$ is even, $i=2j$, and we
call $i=p(l(x))$ the sparsity task if $i$ is odd, $i=2j+1$.

We say that a finite sequence $x$ of length $n$ is $j$-discarded by a sequence
$y$ (or by an edge $\sigma\in G^{n}_{[j]_{1}}$ such that $\sigma_{2}=y$), if
$l(y)=l(x)=n$ and a finite sequence $u$ exist such that $x\sim_{w(i,n)}u$ and
$\tilde{F}_{[j]_{3}}(y)\subseteq u$.

Let us define the first predicate which have to provide the difference between
atoms:

$B_{1}(j,\sigma)\Longleftrightarrow\sum\limits_{z}R_{[j]_{2}}(z)\leq
2^{-\sigma_{1}+3},$ (32)

where by $R_{[j]_{2}}$ we denote the frame of the flow through the elementary
network $q_{[j]_{2}}$ defined on steps $<n$, and the sum is taken over all $z$
of length $l(\sigma_{2})$, which are $j$-discarded by the sequence
$\sigma_{2}$. Here, in the exponent, we identify the sequence $\sigma_{1}$ and
its number.

Let $\phi_{j}$ be a computable sequence of all partial recursive functions
such that for any partial recursive function $f$ there exist infinitely many
$j$ such that $\phi_{j}=f$, $\phi^{n}_{i}(x)$ is a result of computation in
$n$ steps (see Section 2).

Define the second predicate which have to provide the sparsity of sequences
from the support set of the $q_{[j]_{1}}$-flow:

$\displaystyle
B_{2}(j,\sigma)\Longleftrightarrow\sigma_{2}=\sigma_{1}10^{l(\sigma_{2})-l(\sigma_{1})-1}\&l(\sigma_{2})\geq\phi^{l(\sigma_{2})}_{[j]_{1}}(l(\sigma_{1})+2).$

Construction of the network $q_{m}$.

The induction hypothesis is the same as for step $n$ of Template 2.

At any step $n$ of induction we execute the task $i=p(n)$. This means that

1) Let $i=2j$. In this case do the following:

1.1) denote $m=[j]_{1}$ and execute step $n$ of Template 2 with the predicate
$B_{1}(j,\sigma)$ to define the set $G^{n}_{m}$, the values $q_{m}(\sigma)$
for $\sigma\in G^{n}_{m}$ such that $l(\sigma_{2})=n$, and the values of the
flow delay function $s_{m}(x)$ for all $x$ of length $n$;

1.2) denote $m^{\prime}=[j]_{2}$ and define
$G^{n}_{m^{\prime}}=G^{n-1}_{m^{\prime}}$, $s_{m^{\prime}}(x)=1$ for each $x$,
which is $j$-discarded on step $n$ by some edge $\sigma\in
G^{n}_{[j]_{1}}(j)$; define $s_{m^{\prime}}(x)=0$ for all other $x$ such that
$l(x)=n$;

1.3) for each $m$ such that $m\not=[j]_{1}$ and $m\not=[j]_{2}$ define
$G^{n}_{m}=G^{n-1}_{m}$ and $s_{m}(x)=0$ for every $x$ of length $n$.

2) Let $i=2j+1$. In this case do the following:

2.1) denote $m=[j]_{1}$ and execute step $n$ of Template 2 with the predicate
$B_{2}(j,\sigma)$ to define the set $G^{n}_{m}$, the values $q_{m}(\sigma)$
for $\sigma\in G^{n}_{m}$ such that $l(\sigma_{2})=n$, and the values of the
flow delay function $s_{m}(x)$ for all $x$ of length $n$;

2.2) for each $m\not=[j]_{1}$ define $G^{n}_{m}=G^{n-1}_{m}$ and $s_{m}(x)=0$
for every $x$ of length $n$;

3) after all, for every $m$ define
$q_{m}(\sigma)=\frac{1}{2}(1-s_{m}(\sigma_{1}))$ for each $\sigma$ of unit
length such that $l(\sigma_{1})=n$.

This concludes the description of the induction step.

By Lemma 11 $q_{m}(\sigma)=q_{m}(\sigma^{\prime})$ for any
$\sigma,\sigma^{\prime}\in G_{m}$ such that
$\sigma\sim_{w(i,n)}\sigma^{\prime}$.

Let $P_{m}$ be the $q_{m}$-flow. Define ${\bf p}_{m}=[\bar{E}_{P_{m}}]$. By
Lemma 14 $P_{m}({\bf p}_{m})>0$, then ${\bf p}_{m}\not={\bf 0}$.

Define ${\bf h}_{m}=i_{P_{m}}({\bf p}_{m})$ for each $m$. ${\bf
h}_{m}\not={\bf 0}$, since $\bar{P}(i_{P}({\bf p_{m}}))=\bar{P}({\bf p_{m}})$.
The LV-degree ${\bf h}_{m}$ is an atom of $\Upsilon$ for each $m$, since we
use Template 2 for its definition.

By Lemma 15, for $k\not=m$, any $\alpha\in E_{P_{k}}$ and $\beta\in E_{P_{m}}$
do not Turing reducible to each other. Therefore, ${\bf p}_{k}\cap{\bf
p}_{m}={\bf 0}$. Since ${\bf h}_{m}\subseteq{\bf p}_{m}$, we obtain ${\bf
h}_{k}\cap{\bf h}_{m}={\bf 0}$ for $k\not=m$. $\Box$

The rest of the proof of Theorem 7 is presented in the following lemma.

###### Lemma 16

Any infinite sequence $\omega$ from the support set of the semimeasure $P_{m}$
is sparse.

Proof. Let $m$ be given. We should prove that for any infinite sequence
$\omega$ from the support set of the semimeasure $P_{m}$ and for any total
computable function $f$, there are infinitely many $k$ such that the prefix of
$\omega$ of length $f(k)$ contains less than $k$ ones.

For any computable function $f$ there are infinitely many odd $i=2j+1$ such
that $f=\phi_{j}$. Since $f$ is total, each prefix of any $\omega\in
E_{P_{m}}$ has an $j$-extension. By Lemma 5
$\sigma_{1}\subset\sigma_{2}\subset\omega$ for infinitely many extra edges
$\sigma$ such that $f(l(\sigma_{1})+2)\leq l(\sigma_{2})$. Since number of
ones in $\sigma_{2}=\sigma_{1}10^{l(\sigma_{2})-l(\sigma_{1})-1}$ is less or
equal to $l(\sigma_{1})+1$ and $f(l(\sigma_{1})+2)\leq l(\sigma_{2})$, the
prefix of $\omega$ of length $f(l(\sigma_{1})+2)$ contains less than
$l(\sigma_{1})+2$ ones.

Since at least one 1 is added to $\sigma_{1}$ at infinitely many steps, the
sequence $\omega$ contains infinitely many 1s. Hence, each $\omega$ from the
support set of semimeasure $P_{m}$ is sparse. $\Box$

###### Theorem 8

There exists an infinitely divisible element defined by a collection of the
hyperimmune sequences.

The proof is similar to the proof of Theorem 7, where the recursive predicate
$B_{1}$ is replaced with (18) and the Template 1 is used.

Theorems 7 and 8 imply the main result of Section 5.6.

###### Theorem 9

The decomposition ${\bf h}=\cup_{i=1}^{\infty}{\bf h}_{i}\cup{\bf e}$ of
hyperimmune LV-degree takes place, where ${\bf h}_{1},{\bf h}_{2},\dots$ are
infinite sequence of atoms and ${\bf e}$ is the infinitely divisible element
defined by collections of hyperimmune sequences.

It should be interesting to extend the result of Theorem 9 to other specific
LV-degrees. A careful analysis of the relationship between LV-degrees and
Turing degrees is given in the review by Holzl and Porter [4]. We have proved
that some of LV-degrees can be generated using Template 2 and, so, the
decomposition of type (7) takes place for these LV-degrees. For example, this
is the hyperimmune degree. Holzl and Porter [4] result on DNC (diagonally non-
computable) degree can be extended to obtain the decomposition like (7) for
this degree.101010An infinite binary sequence $\omega$ has DNC degree if and
only if there is some function $f$ such that $f\leq_{T}\omega$ and
$f(i)\not=\phi_{i}(i)$ for all $i$.

An open problem arises can we obtain decompositions of type (7) of the LV-
degrees considered in [4] among which there are degrees defined by the
collection of 1-generic sequences, degrees defined by the collection of
generalized low sequences, and those collections corresponding to various
notions of effective randomness. Author does not know whether it is possible
to apply the technics of Templates 1 and 2 for the construction of LV-degrees
of 1-generic sequences.

## References

  * [1] Bienvenu, L., Patey, L. Diagonally non-computable functions and fireworks. Information and Computation, 253 (2017) 64–77.
  * [2] Cover T.M., Gács P., Gray R.M. Kolmogorov’s contributions to information theory and algorithmic complexity. Annals of Probability 17 (1) (1989) 840–865.
  * [3] Downey, R., Hirschfeldt, D. Algorithmic randomness and complexity. Springer, 2010.
  * [4] Holzl, R., Porter, C.P. Degrees of Randomized Computability. arXiv:1907.07815v3 (2021).
  * [5] Gács, P. Lecture notes on descriptional complexity and randomness, Boston University, http://www.cs.bu.edu/ gacs/papers/ait-notes.pdf (1997).
  * [6] de Leeuw, K., Moore, E.F., Shannon, C.E., Shapiro, N. Computability by Probabilistic Machines. – In: _Automata studies_ , edited by C.E. Shannon and J. McCarthy, _Annals of Mathematics Studies_ , 34, lithoprinted, Princeton University Press (1956) 183–212.
  * [7] Levin, L.A., V’yugin, V.V. Invariant properties of informational bulks. _MFCS 1977: Mathematical Foundations of Computer Science_. _Lecture Notes on Computer Science_ , 53, Springer (1977) 359–364.
  * [8] Levin, L.A. Randomness conservation inequalities; information and independence in mathematical theories. _Information and Control_ , 61(1) (1984) 15–37.
  * [9] Li, M., Vitányi, P. An Introduction to Kolmogorov Complexity and Its Applications, 3rd ed. New York: Springer–Verlag. 2008.
  * [10] Martin-Löf, P. The definition of random sequences. _Information and Control_ , 9 (1966) 602–619.
  * [11] Nies, A. Computability and randomness. Oxford University Press. 2009.
  * [12] Rogers, H. Theory of Recursive Functions and Effective Computability. New York: McGraw Hill. 1967.
  * [13] Rumyantsev, A. Shen, A. Probabilistic constructions of computable objects and a computable version of Lov’asz Local Lemma. Fundamenta Informaticae, 132(1) (2014) 1–14.
  * [14] Sacks, G.E. Degrees of unsolvability. Princeton University Press, 1963.
  * [15] Shen, A., Uspensky, V.A., Vereshchagin, N.K. Kolmogorov complexity and algorithmic randomness. Mathematical Surveys and Monographs, American Mathematical Society 220 (2017) http://lpes.math.msu.su/ ver/kolm-book. 2007
  * [16] Shiryaev, A.N. Probability Berlin: Springer. 1980.
  * [17] Soare, R.I. Turing computability. In Theory and Applications of Computability. Springer. 2016.
  * [18] Solomonoff, R.J. A formal theory of inductive inference, Part I. Information and Control, 7(1) (1964) 1–22.
  * [19] Solomonoff, R.J. A formal theory of inductive inference, Part II. Information and Control, 7(2) (1964) 224–254.
  * [20] Solomonoff R.J. Complexity-based induction systems: Comparisons and convergence theorems. IEEE Transactions on Information Theory. IT-24 (1978) 422–432.
  * [21] V’jugin, V.V. On Turing invariant sets. _Soviet Mathematics Doklady_ , 17 (1976) 1090–1094.
  * [22] V’yugin, V.V. Algebra of Invariant Properties of Binary Sequences, _Problems Inform. Transmission_ , 18(2) (1982) 147–161.
  * [23] V’yugin, V.V. On calibration error of randomized forecasting algorithms. Theoretical Computer Science, 410(19) (2009) 1781–1795.
  * [24] V’yugin, V.V. On empirical meaning of randomness with respect to parametric families of probability distributions. Theory of Computing Systems, 50(2) (2012) 296–312.
  * [25] Uspensky, V.A., Semenov, L.A., Shen, A. Can an individual sequence of zeros and ones be random? Russian Math. Surveys 45 (1990) 121–189.
  * [26] Zvonkin, A.K., Levin, L.A. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. _Russian Math. Surveys_ , 25(6) (1970) 83–124.