# Bridging Computational Notions of Depth

Laurent Bienvenu, Christopher P. Porter

###### Abstract.

In this article, we study the relationship between notions of depth for
sequences, namely, Bennett’s notions of strong and weak depth, and deep
$\Pi^{0}_{1}$ classes, introduced by the authors and motivated by previous
work of Levin. For the first main result of the study, we show that every
member of a $\Pi^{0}_{1}$ class is order-deep, a property that implies strong
depth. From this result, we obtain new examples of strongly deep sequences
based on properties studied in computability theory and algorithmic
randomness. We further show that not every strongly deep sequence is a member
of a deep $\Pi^{0}_{1}$ class. For the second main result, we show that the
collection of strongly deep sequences is negligible, which is equivalent to
the statement that the probability of computing a strongly deep sequence with
some random oracle is 0, a property also shared by every deep $\Pi^{0}_{1}$
class. Finally, we show that variants of strong depth, given in terms of a
priori complexity and monotone complexity, are equivalent to weak depth.

##  1\. Introduction

Bennett introduced the notion of logical depth in [Ben95] as a measure of
complexity, formulated in terms the amount of computation time required to
reproduce a given object. Whereas the Kolmogorov complexity of a string
$\sigma\in 2^{<\omega}$ measures the length of the shortest input given to a
fixed universal machine that reproduces $\sigma$ as its output, logical depth
measures the number of steps it takes to recover $\sigma$ from this shortest
input. Bennett further defined a sequence $X\in 2^{\omega}$ to be strongly
deep if for every computable function $t$ the logical depth of almost all of
the initial segments $X{\upharpoonright}n$ of $X$ is greater than $t(n)$.

Bennett established several fundamental facts about strongly deep sequences,
namely that the halting set $K$ is strongly deep, that no computable sequence
and no Martin-Löf random sequence is strongly deep, and that strong depth is
closed upwards under truth-table reducibility (a result he referred to as the
_slow growth law_). Bennett further introduced the notion of weak depth, where
a sequence is weakly deep if it is not truth-table reducible to a random
sequence.

An analogue of deep sequences for $\Pi^{0}_{1}$ classes, i.e., effectively
closed subsets of $2^{\omega}$, was developed by the present authors in
[BP16]. The authors isolated the notion of a deep $\Pi^{0}_{1}$ class as a
generalized of work of Levin [Lev13], who implicitly showed that the
$\Pi^{0}_{1}$ class of consistent completions of Peano arithmetic is deep. The
basic idea, made precise in the next section, is that a $\Pi^{0}_{1}$ class
$\mathcal{P}$ is deep if the probability of computing some length $n$ initial
segment of some member of $\mathcal{P}$ via some Turing functional equipped
with a random oracle rapidly approaches zero as $n$ grows without bound. In
[BP16], the authors proved a number of results about deep $\Pi^{0}_{1}$
classes, including an analogue of the slow growth law for deep $\Pi^{0}_{1}$
classes in the Medvedev degrees, as well as identifying a number of examples
of deep $\Pi^{0}_{1}$ classes based on properties studied in computability
theory and algorithmic information theory.

The aim of this study is to show that the relationship between strongly deep
sequences and deep $\Pi^{0}_{1}$ classes is no mere analogy. In particular, we
prove that every member of a deep $\Pi^{0}_{1}$ class is strongly deep, from
which it follows that we gain a significant number of newly identified
examples of strongly deep sequences based on results from [BP16]. We further
show that a strongly deep sequence need not be a member of a deep
$\Pi^{0}_{1}$ class. Next, as every deep $\Pi^{0}_{1}$ class is negligible, in
the sense that the probability of computing a member of such a class with a
Turing functional equipped with a random oracle is zero, in light of the fact
that all members of deep $\Pi^{0}_{1}$ classes are strongly deep, it is
reasonable to ask whether the collection of strongly deep sequences is
negligible. We answer this question in the affirmative, while further showing
that the collection of sequences that are deep with respect to any fixed time
bound is not negligible. Finally, we consider variants of strong depth given
in terms of a priori and monotone complexity and demonstrate that these two
variants are equivalent to Bennett’s notion of weak depth (with the latter
equivalence following from work by Schnorr and Fuchs [SF77]).

One takeaway we aim to emphasize in this study is the importance of the slow
growth law for the study of depth, akin to the role of randomness preservation
in the study of algorithmic randomness. According to the latter, every
sequence that is truth-table reducible to a sequence that is random with
respect to a computable measure is itself random with respect to a computable
measure, which is precisely the dual of the slow growth law for deep
sequences. We anticipate that the slow growth law will continue to be a useful
tool in the study of notions of depth.

The outline of the remainder of this article is as follows. In Section 2 we
provide background on notions from computability theory and algorithmic
randomness that we draw upon in this study. Next, in Section 3, we provide a
short proof of the slow growth law for strongly deep sequence and use it to
identify some hitherto unnoticed examples of strongly deep sequences from
classical computability theory. In Section 4 we prove the main result of our
study, namely that every member of a deep $\Pi^{0}_{1}$ class is strongly
deep. Here we observe some consequences of this result and separate several
depth notions, showing in particular that not every strongly deep sequence is
a member of a deep $\Pi^{0}_{1}$ class. Section 5 contains our second main
result, that the collection of strongly deep sequences is negligible, while in
Section 6 we show the equivalence of depth notions given in terms of a priori
and monotone complexity with Bennett’s notion of weak depth.

##  2\. Background

###  2.1. Turing functionals

Recall that a _Turing functional_ $\Phi:\subseteq 2^{\omega}\rightarrow
2^{\omega}$ can be defined in terms of a c.e. set $S_{\Phi}$ of pairs of
strings $(\sigma,\tau)$ such that if
$(\sigma,\tau),(\sigma^{\prime},\tau^{\prime})\in S_{\Phi}$ and
$\sigma\preceq\sigma^{\prime}$, then $\tau\preceq\tau^{\prime}$ or
$\tau^{\prime}\preceq\tau$. For each $\sigma\in 2^{<\omega}$, we define
$\Phi^{\sigma}$ to be the maximal string in
$\\{\tau:(\exists\sigma^{\prime}\preceq\sigma)(\sigma^{\prime},\tau)\in
S_{\Phi}\\}$ in the order given by $\preceq$. To obtain a map defined on
$2^{\omega}$ from the set $S_{\Phi}$, for each $X\in 2^{\omega}$, we let
$\Phi^{X}$ be the maximal $y\in 2^{<\omega}\cup 2^{\omega}$ in the order given
by $\preceq$ such that $\Phi^{X{\upharpoonright}n}$ is a prefix of $y$ for all
$n$.

###  2.2. Semimeasures

A _discrete semimeasure_ is a function $m:2^{<\omega}\rightarrow[0,1]$
satisfying $\sum_{\sigma\in 2^{<\omega}}m(\sigma)\leq 1$. Similarly, _a
continuous semimeasure_ is a function $P:2^{<\omega}\rightarrow[0,1]$
satisfying (i) $P(\varnothing)\leq 1$ and (ii) $P(\sigma)\geq P(\sigma
0)+P(\sigma 1)$ for all $\sigma\in 2^{<\omega}$. Given a continuous
semimeasure $P$ and some $S\subseteq 2^{<\omega}$, we set
$P(S)=\sum_{\sigma\in S}P(\sigma)$.

A discrete semimeasure $m$ is computable if its output values $m(\sigma)$ are
computable uniformly in the input $\sigma\in 2^{<\omega}$ (and similarly for
continuous semimeasures). Here we will also consider _lower semicomputable_
semimeasures (both discrete and continuous), where a function
$f:2^{<\omega}\rightarrow[0,1]$ is lower semicomputable if each value
$f(\sigma)$ is the limit of a computable, nondecreasing sequence of rationals,
uniformly in $\sigma\in 2^{<\omega}$.

An important development due to Levin [LZ70] was the identification of
_universal_ semimeasures: for discrete semimeasures, $m$ is universal if for
every lower semicomputable measure $m_{0}$ there is some constant $c$ such
that $m_{0}(\sigma)\leq c\cdot m(\sigma)$. Similarly, a continuous semimeasure
$M$ is universal if for every lower semicomputable measure $P$ there is some
constant $c$ such that $P(\sigma)\leq c\cdot M(\sigma)$. Hereafter,
$\mathbf{m}$ and $\mathbf{M}$ will denote fixed universal discrete and
continuous semimeasures, respectively.

###  2.3. Initial segment complexity

Recall that the prefix-free Kolmogorov complexity of a string $\tau\in
2^{<\omega}$ is defined by setting $K(\tau)=\min\\{|\sigma|\colon
U(\sigma){\downarrow}=\tau\\}$, where $U$ is a fixed universal prefix-free
machine (i.e., recall that a machine $M$ is prefix-free if for $\sigma,\rho\in
2^{<\omega}$, if $M(\sigma){\downarrow}$ and $\sigma\prec\rho$, then
$M(\rho){\uparrow}$). Moreover, we can define time-bounded versions of
Kolmogorov complexity. A function $t:\omega\rightarrow\omega$ is called a
_time bound_ if $t$ is total and non-decreasing. Then for a fixed computable
time bound $t$, the $t$-time-bounded complexity of $\tau\in 2^{<\omega}$ is
defined by setting $K^{t}(\tau)=\min\\{|\sigma|\colon
U(\sigma){\downarrow}=\tau\text{\;in $\leq t(|\tau|)$ steps}\\}$.

Note that by Levin’s coding theorem, $K(\sigma)=-\log\mathbf{m}(\sigma)+O(1)$
for all $\sigma\in 2^{<\omega}$. A similar relationship holds for computable
discrete semimeasures and time-bounded Kolmogorov complexity. First, we define
a time-bounded version of $\mathbf{m}$ as follows. As $\mathbf{m}$ is lower
semicomputable, for each $s\in\omega$, we have an approximation
$\mathbf{m}_{s}$ of $\mathbf{m}$ (i.e., for each $\sigma\in 2^{<\omega}$,
$\mathbf{m}_{s}(\sigma)$ is the $s$-th rational number in computable sequence
that converges to $\mathbf{m}(\sigma)$). Then given a computable time bound
$t$, we set $\mathbf{m}^{t}(\sigma)=\mathbf{m}_{t(|\sigma|)}$, which is
clearly a computable semimeasure. We will make use of the following lemma from
[BDM23] (where for functions $f,g$, $f\leq^{\times}g$ means that there is some
$c$ such that $f(n)\leq c\cdot g(n)$ for all $n\in\omega$).

######  Lemma 1 ([BDM23]).

  * (i)

For every computable discrete semimeasure $m$, there is some computable time
bound $t$ such that $m\leq^{\times}\mathbf{m}^{t}$.

  * (ii)

For every computable time bound $t$, $2^{-K^{t}}$ is a computable discrete
semimeasure.

  * (iii)

For every computable time bound $t$, there is some computable time bound
$t^{\prime}$ such that $2^{-K^{t}}\leq^{\times}\mathbf{m}^{t^{\prime}})$.

In addition, we need the following theorem (see, e.g. [JLL94, Theorem
4.3(2)]).

######  Theorem 2.

For every computable time bound $t$, there is a computable time bound
$t^{\prime}$ such that $\mathbf{m}^{t}\leq^{\times}2^{-K^{t^{\prime}}}$.

Note that by combining Lemma 1(iii) and Theorem 2, we obtain a resource-
bounded analogue of Levin’s coding theorem.

In the case of continuous semimeasures, we directly define
$\mathit{KA}(\sigma):=-\log\mathbf{M}(\sigma)$ to be the _a priori complexity_
of $\sigma\in 2^{<\omega}$. Just as we defined $\mathbf{m}^{t}$ for any
computable time bound $t$, we can similarly define $\mathbf{M}^{t}$, which is
a computable continuous semimeasure. Moreover, we can establish the analogue
of Lemma 1(i): For every computable continuous semimeasure $P$, there is some
computable time bound $t$ such that $P\leq^{\times}\mathbf{M}^{t}$. We will
also define $\mathit{KA}^{t}:=\mathbf{M}^{t}$ for any given computable time
bound $t$.

Lastly, we define monotone complexity in terms of monotone machines, where a
monotone machine $M:2^{<\omega}\rightarrow 2^{<\omega}$ satisfies the property
that for $\sigma,\tau\in\mathrm{dom}(M)$, if $\sigma\preceq\tau$, then either
$M(\sigma)\preceq M(\tau)$ or $M(\tau)\preceq M(\sigma)$. Given a universal
monotone machine $U$, we set $\mathit{Km}(\tau)=\min\\{|\tau|\colon
U(\sigma){\downarrow}\succeq\tau\\}$. Given a computable time bound, we can
also define $\mathit{Km}^{t}$ in the obvious way.

###  2.4. Randomness and depth notions

Given a computable measure $\mu$ on $2^{\omega}$ (i.e., a measure on
$2^{\omega}$ where the values $\mu(\llbracket\sigma\rrbracket)$ are computable
uniformly in $\sigma\in 2^{<\omega}$), recall that a _$\mu$ -Martin-Löf test_
is a uniformly $\Sigma^{0}_{1}$ sequence $(U_{i})_{i\in\omega}$ such that
$\mu(U_{i})\leq 2^{-i}$. Recall further that a sequence $X\in 2^{\omega}$
passes the test $(U_{i})_{i\in\omega}$ if $X\notin\bigcap_{i\in\omega}U_{i}$
and $X$ is _$\mu$ -Martin-Löf random_ if it passes all $\mu$-Martin-Löf tests.
In the case that $\mu$ is the Lebesgue measure on $2^{\omega}$ (which we
denote by $\lambda$), we will refer to $\lambda$-Martin-Löf random sequences
simply as Martin-Löf random sequences.

Next, $X\in 2^{\omega}$ is _strongly deep_ if for every computable time bound
$t$, we have
$K^{t}(X{\upharpoonright}n)-K(X{\upharpoonright}n)\rightarrow\infty$. A
slightly stronger notion is given by order-depth, where $X\in 2^{\omega}$ is
_order-deep_ if there is a computable order function
$g:\omega\rightarrow\omega$ such that
$K^{t}(X{\upharpoonright}n)-K(X{\upharpoonright}n)\geq g(n)$ for almost every
$n\in\omega$. Here we use the term ‘order function’, or simply ‘order’ to mean
a non-decreasing and unbounded function. When $h$ is such a function,
$h^{-1}(k)$ denotes the smallest $n$ such that $h(n)\geq k$. Note that
$h^{-1}$ is computable when $h$ is.

In the rest of the paper we will sometimes use an equivalent characterization
of order-depth, given by the following lemma.

######  Lemma 3.

For $X\in 2^{\omega}$, the following are equivalent.

  * (i)

$X$ is order-deep

  * (ii)

For some computable increasing function $h$, for any computable time bound $t$
and almost all $n$,
$K^{t}(X{\upharpoonright}h(n))-K(X{\upharpoonright}h(n))\geq^{+}n$.

  * (iii)

For some computable increasing function $h$, for any computable time bound $t$
and almost all $n$,
$\frac{\mathbf{m}(X{\upharpoonright}h(n))}{\mathbf{m}^{t}(X{\upharpoonright}h(n))}\geq^{\times}2^{n}$.

The proof of this lemma is technical; for the sake of readability, we defer it
to the appendix.

One of the key properties of strong depth is the slow growth law, given in
terms of truth-table reductions. Recall that a $\mathit{tt}$-functional is a
Turing functional that is total on all oracles; equivalently, there is a
computable function $f$ such that for all $X\in 2^{\omega}$,
$|\Phi^{X{\upharpoonright}f(n)}|\geq n$.

######  Theorem 4 (Slow Growth Law [Ben95]).

For $X,Y\in 2^{\omega}$, if $X$ is strongly deep and $X\leq_{\mathit{tt}}Y$,
then $Y$ is strongly deep.

The slow growth law also holds for order-depth.

Bennett proved that no computable sequence and no Martin-Löf random sequence
is strongly deep. Hereafter, we will refer to sequences that are not strongly
deep as being _shallow_. Bennett further showed that the halting set
$\emptyset^{\prime}=\\{e:\phi_{e}(e){\downarrow}\\}$ (where
$(\phi_{e})_{e\in\omega}$ is a standard enumeration of the partial computable
functions) is strongly deep.

Bennett defined a weaker notion of depth: a sequence $X\in 2^{\omega}$ is
_weakly deep_ if $X$ is not $\mathit{tt}$-reducible to a Martin-Löf random. By
the slow growth law and the fact that no Martin-Löf random sequences are
strongly deep, it follows that every strongly deep sequence is weakly deep; as
shown by Bennett [Ben95], the converse does not hold. Note that it is a
folklore result that a sequence is not truth-table reducible to a Martin-Löf
random sequence if and only if it is not random with respect to a computable
measure, thereby providing an alternative characterization of weak depth.

###  2.5. Deep $\Pi^{0}_{1}$ classes and negligiblity

As noted in the introduction, the authors in [BP16] introduced the notion of a
deep $\Pi^{0}_{1}$ class as the abstraction of a phenomenon first isolated by
Levin in [Lev13] Given a $\Pi^{0}_{1}$ class $\mathcal{P}$, recall that there
is a canonical co-c.e. tree $T\subseteq 2^{<\omega}$ such that
$\mathcal{P}=[T]$, i.e., $\mathcal{P}$ is the collection of all infinite paths
through $T$; more specifically, this tree $T$ is the set of all initial
segments of members of $\mathcal{P}$. For $n\in\omega$, let $T_{n}$ be the set
of all strings in $T$ of length $n$. We say that a $\Pi^{0}_{1}$ class
$\mathcal{P}$ is _deep_ if there is some order $g$ such that
$\mathbf{M}(T_{n})\leq 2^{-g(n)}$. Equivalently, $\mathcal{P}$ is deep is
there is some order $h$ such that $\mathbf{M}(T_{h(n)})\leq 2^{-n}$.

An analogue of the slow growth law holds for deep $\Pi^{0}_{1}$ classes in a
suitable degree structure, namely the strong degrees (also referred to as the
Medvedev degrees). Given $\Pi^{0}_{1}$ classes $\mathcal{P}$ and
$\mathcal{Q}$, we say that $\mathcal{P}$ is strongly reducible to
$\mathcal{Q}$, written $\mathcal{P}\leq_{s}\mathcal{Q}$, if there is some
Turing functional $\Phi$ such that for every $Y\in\mathcal{Q}$, there is some
$X\in\mathcal{P}$ such that $X=\Phi(Y)$; equivalently, we have
$\Phi(\mathcal{Q})=\mathcal{P}$. As noted in [BP16], we can assume here that
$\Phi$ is a $\mathit{tt}$-functional, a fact that will be useful in this
study. Then we have:

######  Theorem 5 (Slow Growth Law for $\Pi^{0}_{1}$ classes, [BP16]).

For $\Pi^{0}_{1}$ classes $\mathcal{P},\mathcal{Q}\subseteq 2^{\omega}$, if
$\mathcal{P}$ is deep and $\mathcal{P}\leq_{s}\mathcal{Q}$, then $\mathcal{Q}$
is deep.

Depth for $\Pi^{0}_{1}$ classes implies a property that holds more broadly for
subsets of $2^{\omega}$, namely the property of being negligible. First,
observe that a lower semicomputable semimeasure $P$ can be trimmed back to a
measure $\overline{P}\leq P$ (see [BHPS14] details). In particular, we can
trim back the universal lower semicomputable semimeasure $\mathbf{M}$ to get a
measure $\mathbf{\overline{M}}$. One key result concerning
$\mathbf{\overline{M}}$ is that for a measurable set $\mathcal{A}\subseteq
2^{\omega}$, $\mathbf{\overline{M}}(\mathcal{A})=0$ if and only if
$\lambda(\\{X:(\exists Y\in\mathcal{A})\;Y\leq_{T}X\\})=0$; that is, from the
point of view of Lebesgue measure, only relatively few sequences can compute
of member of $\mathcal{A}$. Following Levin (see for example [Lev84]), we call
such sets $\mathcal{A}$ _negligible_. As we can equivalently consider the
collection of random sequences that compute a member of $\mathcal{A}$, we can
recast negligibility in terms of probabilistic computation: a collection
$\mathcal{A}$ is negligible if the probability of probabilistically computing
a member of $\mathcal{A}$ is zero. Note that every deep $\Pi^{0}_{1}$ class is
thus negligible; in fact, we can interpret the property of depth for a
$\Pi^{0}_{1}$ class $\mathcal{P}$ as the property that the probability of
computing the first $n$ bits of a member of $\mathcal{P}$ converges to 0
effectively in $n\in\omega$. As shown in [BP16], not every negligible
$\Pi^{0}_{1}$ class is deep.

Two other notions related to depth and negligibility for $\Pi^{0}_{1}$ classes
studied in [BP16] are the notions of $\mathit{tt}$-depth and
$\mathit{tt}$-negligibility:

  * •

A $\Pi^{0}_{1}$ class $\mathcal{P}$ with canonical co-c.e. tree $T$ is
_$\mathit{tt}$ -deep_ if for every computable measure $\mu$ there is some
computable order $g$ such that $\mu(T_{n})\leq 2^{-g(n)}$ for all
$n\in\omega$, or equivalently, for every computable measure $\mu$, there is
some computable order $h$ such that $\mu(T_{h(n)})\leq 2^{-n}$.

  * •

A measurable set $\mathcal{C}\subseteq 2^{\omega}$ is _$\mathit{tt}$
-negligible_ if $\mu(\mathcal{C})=0$ for every computable measure $\mu$, or
equivalently, $\lambda(\\{X\in\mathcal{C}\colon\exists Y\in
2^{\omega}\;X\leq_{\mathit{tt}}Y\\})=0$.

Unlike the notions of depth and negligibility, we have the following
equivalence:

######  Theorem 6 ([BP16]).

Let $\mathcal{P}\subseteq 2^{\omega}$ be a $\Pi^{0}_{1}$ class. The following
are equivalent:

  * (i)

$\mathcal{P}$ is $\mathit{tt}$-deep.

  * (ii)

$\mathcal{P}$ is $\mathit{tt}$-negligible.

  * (iii)

For every computable measure $\mu$ on $2^{\omega}$, $\mathcal{P}$ contains no
$\mu$-Martin-Löf random element.

Note that by the alternative characterization of weak depth discussed in the
previous subsection, Theorem 6, a $\Pi^{0}_{1}$ class is $\mathit{tt}$-deep if
and only if all of its members are weakly deep.

##  3\. On the Slow Growth Law

In this section, we provide a proof of the slow growth law and provide some
hitherto unobserved consequences of the result. In particular, the proof of
the slow growth law that we offer here is distinct from others in the
literature in two respects. First, unlike other proofs in the literature, such
as the one found in [JLL94], which are more complexity-theoretic (using the
machinery of Kolmogorov complexity), our proof is measure-theoretic, being
based on computable semimeasures. Second, the proof offered here is much more
direct than currently available proofs of the slow growth law.

We begin with a few words to simplify the setting. First, as noted in the
previous section $X\in 2^{\omega}$ is strongly deep when

$K^{t}(X{\upharpoonright}n)-K(X{\upharpoonright}n)\rightarrow\infty$

for every computable time bound $t$, but a more pleasant way to rephrase this,
by elevating to the power of $2$ on both sides, is to require that

$\frac{\mathbf{m}(X{\upharpoonright}n)}{p(X{\upharpoonright}n)}\rightarrow\infty$

for every computable discrete semi-measure $p$ (that the two phrasings are
equivalent follows directly from Lemma 1 and Theorem 2).

Second, if $\Gamma$ is a tt-functional with use $\gamma$, we can naturally
extend $\Gamma$ to strings by defining $\Gamma(\sigma)$ to be the first $n$
bits of $\Gamma^{\sigma}$, where $n$ is such that
$|\sigma|\in[\gamma(n),\gamma(n+1))$. Seen as a function on strings, $\Gamma$
has two properties that we will need:

  * (i)

$\Gamma$ is total;

  * (ii)

For every string $\tau$, the preimage $\Gamma^{-1}(\tau)$ is a finite set that
can be computed uniformly in $\tau$.

We are now ready to prove our main theorem.

######  Theorem 7.

Let $F$ be total computable function on strings such that for all $\tau$,
$F^{-1}(\tau)$ is a finite set which can be computed uniformly in $\tau$. Let
$p$ be a computable discrete semimeasure. Then, there exists a computable
discrete semimeasure $q$ such that

$\frac{\mathbf{m}(F(\sigma))}{q(F(\sigma))}\leq^{\times}\frac{\mathbf{m}(\sigma)}{p(\sigma)}$

It is now clear that this theorem implies the slow growth law with $F$
identified with the extension of $\Gamma$ to $2^{<\omega}$, setting
$\sigma=X{\upharpoonright}n$, and letting $n$ tend to $\infty$. Let us prove
the theorem.

###### Proof.

Define $q$ simply as the push-forward measure of $p$ under $F$:

$q(\tau)=\sum_{\sigma\in F^{-1}(\tau)}p(\sigma)$

Our assumption on $F$ and $p$ imply that $q$ is computable. It is a
semimeasure as $\sum_{\tau}q(\tau)=\sum_{\tau}\sum_{\sigma\in
F^{-1}(\tau)}p(\sigma)=\sum_{\sigma}p(\sigma)\leq 1$.

Now, define for all $\sigma$:

$m(\sigma)=\frac{\mathbf{m}(F(\sigma))}{q(F(\sigma))}\cdot p(\sigma)$

We claim that $m$ is a lower semicomputable discrete semimeasure. That $m$ is
lower semicomputable is clear, since $\mathbf{m}$ is lower semicomputable and
$p,q,$ and $F$ are computable. That $m$ is a discrete semimeasure can be
established as follows:

$\sum_{\sigma}m(\sigma)=\sum_{\tau}\sum_{\sigma\in
F^{-1}(\tau)}m(\sigma)=\sum_{\tau}\sum_{\sigma\in
F^{-1}(\tau)}\frac{\mathbf{m}(F(\sigma))}{q(F(\sigma))}\cdot p(\sigma)$
$=\sum_{\tau}\frac{\mathbf{m}(\tau)}{q(\tau)}\cdot\left(\sum_{\sigma\in
F^{-1}(\tau)}p(\sigma)\right)=\sum_{\tau}\frac{\mathbf{m}(\tau)}{q(\tau)}\cdot
q(\tau)=\sum_{\tau}\mathbf{m}(\tau)\leq 1.$

By maximality of $\mathbf{m}$, we have
$m(\sigma)\leq^{\times}\mathbf{m}(\sigma)$, which by definition of $m$ gives
the desired inequality. ∎

We note in passing that our proof also implies the slow growth law for order-
depth: indeed if in the above we have
$\frac{\mathbf{m}(\Gamma^{X}{\upharpoonright}n)}{q(\Gamma^{X}{\upharpoonright}n)}\geq
h(n)$ for some computable order $h$, then
$\frac{\mathbf{m}(X{\upharpoonright}\gamma(n))}{p(X{\upharpoonright}\gamma(n))}\geq
h(n)$ where $\gamma$ is the use of $\Gamma$, which by Lemma 3 shows that $X$
is order-deep.

We note here some previously unnoticed consequence of slow growth law. First,
observe that the standard unsolvable problems from computability theory are
strongly deep, including:

  * •

Fin = $\\{x:W_{x}\text{ is finite}\\}$

  * •

Inf =$\\{x:W_{x}\text{ is infinite}\\}$

  * •

Tot = $\\{x:\phi_{x}\text{ is total}\\}$

  * •

Cof = $\\{x:W_{x}\text{ is cofinite}\\}$

  * •

Comp = $\\{x:W_{x}\text{ is computable}\\}$

  * •

Ext $\\{x:\phi_{x}\text{ is extendible to a total computable function}\\}$

Indeed, for each such class $C$, we have $\emptyset^{\prime}\leq_{1}C$, i.e.,
there is a computable function $f:\omega\rightarrow\omega$ such that
$n\in\emptyset^{\prime}$ if and only if $f(n)\in C$ for all $n\in\omega$.
Since every 1-reduction defines a $\mathit{tt}$-functional, the result follows
from the slow growth law and the fact that $\emptyset^{\prime}$ is strongly
deep.

In fact, we can strengthen this observation for _all_ non-trivial index sets,
thereby strengthening Rice’s theorem in terms of strong depth:

######  Theorem 8.

If $C\subseteq\omega$ is a shallow index set, i.e., $C$ is not strongly deep,
then either $C=\emptyset$ or $C=\omega$.

This follows immediately from the classical version of Rice’s theorem, for if
$C$ is a non-trivial index set, then either $\emptyset^{\prime}\leq_{1}C$ or
$\overline{}\emptyset^{\prime}\leq_{1}C$. Since
$\overline{}\emptyset^{\prime}$ is strongly deep by the slow growth law, the
result is clear.

We will see additional applications of the slow growth law in the remaining
sections.

##  4\. Members of deep $\Pi^{0}_{1}$ classes

When deep $\Pi^{0}_{1}$ classes were defined in [BP16], the authors referred
to the notion as a type of depth in analogy with Bennett’s original notion of
logical depth (as, for instance, an analogue of the slow growth law for deep
$\Pi^{0}_{1}$ classes was established in [BP16]). We now show that the
connection between these two depth notions is much closer than merely
satisfying an analogy, as we prove that the members of deep $\Pi^{0}_{1}$
classes are strongly deep; in fact, we prove the stronger result that all such
members are order-deep. Note that this is analogous to the result that every
member of a $tt$-deep $\Pi^{0}_{1}$ class is weakly deep, a consequence of
Theorem 6 discussed at the end of Section 2.5.

######  Theorem 9.

Every member of a deep $\Pi^{0}_{1}$ class $\mathcal{P}$ is order-deep.

###### Proof.

Let $T$ be the canonical co-c.e. tree associated to the $\Pi^{0}_{1}$ class
$\mathcal{P}$. Let $h$ be a computable order such that

$\sum_{\sigma\in T_{h(n)}}\mathbf{M}(\sigma)\leq 2^{-2n}.$

for all $n$.

Let $t$ be a computable time bound. By virtue of the inequalities
$\mathbf{M}\geq^{\times}\mathbf{m}\geq^{\times}\mathbf{m}^{t}$, the above
inequality implies

$\sum_{\sigma\in T_{h(n)}}\mathbf{m}^{t}(\sigma)\leq 2^{-2n}.$

Since $\mathbf{m}^{t}$ is computable and $T$ is co-c.e., one can effectively
compute a sequence $s_{n}$ such that

$\sum_{\sigma\in T_{h(n)[s_{n}]}}\mathbf{m}^{t}(\sigma)\leq 2^{-2n}.$

Let now $p$ be the computable discrete semimeasure defined by
$p(\tau)=2^{n}\cdot\mathbf{m}^{t}(\tau)$ if $\tau$ belongs to
$T_{h(n)}[s_{n}]$ for some $n>0$, and $p(\tau)=0$ otherwise. That $p$ is
computable is clear from the definition (and the computability of the sequence
$s_{n}$), and that it is a semimeasure follows from

$\sum_{\tau}p(\tau)=\sum_{n>0}\sum_{\tau\in
T_{h(n)}[s_{n}]}2^{n}\cdot\mathbf{m}^{t}(\tau)\leq\sum_{n>0}2^{n}\cdot
2^{-2n}\leq 1.$

Now, if $X$ is a member of $\mathcal{P}$, that is, $X$ is a path through $T$,
then for each $n>0$, we have $X{\upharpoonright}h(n)\in T_{h(n)}$ and thus

$p(X{\upharpoonright}h(n))=2^{n}\cdot\mathbf{m}^{t}(X{\upharpoonright}h(n)).$

As $\mathbf{m}\geq^{\times}p$ (because $p$ is a discrete semi-measure), we
have

$\mathbf{m}(X{\upharpoonright}h(n))\geq^{\times}2^{n}\cdot\mathbf{m}^{t}(X{\upharpoonright}h(n))$

By Lemma 3, we can conclude that $X$ is order-deep. ∎

One immediate consequence of Theorem 9 is the following.

######  Corollary 10.

If $\mathcal{P}$ is a deep $\Pi^{0}_{1}$ class, then the canonical co-c.e.
tree $T$ associated with $\mathcal{P}$ is order-deep.

###### Proof.

Let $X\in\mathcal{P}$ be the leftmost path through $\mathcal{P}$, which is
order-deep by Theorem 9. Then if $T$ is the canonical co-c.e. tree associated
with $\mathcal{P}$, we have $X\leq_{tt}T$, so by the slow growth law, $T$ is
order-deep. ∎

The converse of this result does not hold.

######  Theorem 11.

There is an order-deep co-c.e. tree $T$ such that $[T]$ is not a deep
$\Pi^{0}_{1}$ class.

###### Proof.

Let $S\subseteq 2^{<\omega}$ be any order-deep co-c.e. tree and let
$T=0^{\frown}S\cup 1^{\frown}2^{<\omega}$. Clearly $T$ is a co-c.e. tree
because $S$ is. To see that $T$ is order-deep, note that $\sigma\in S$ if and
only if either (i) $\sigma$ is the empty string or (ii) $0\preceq\sigma$ and
$\sigma\in T$. It thus follows that $S\leq_{tt}T$, and so by the slow growth
law, $T$ is order-deep. Finally, as the sequence $1^{\omega}$ is a member of
the $\Pi^{0}_{1}$ class $[T]$ and every member of a deep $\Pi^{0}_{1}$ class
must be order-deep by Theorem 9, it follows that $[T]$ cannot be deep.

∎

A similar pair of results hold for $\mathit{tt}$-deep $\Pi^{0}_{1}$ classes.

######  Theorem 12.

If $\mathcal{P}$ is a $\mathit{tt}$-deep $\Pi^{0}_{1}$ class, then the
canonical co-c.e. tree $T$ associated with $\mathcal{P}$ is weakly deep.

###### Proof.

Given a $\Pi^{0}_{1}$ class $\mathcal{P}$ with canonical co-c.e. tree $T$,
suppose that $T$ is not weakly deep. Then $T$ is Martin-Löf random with
respect to some computable measure. As in the proof of Corollary 10, if
$X\in\mathcal{P}$ is the leftmost path through $\mathcal{P}$, then have
$X\leq_{tt}T$. By randomness preservation (according to which if $Y$ is
Martin-Löf random with respect to a computable measure and
$X\leq_{\mathit{tt}}Y$, then $X$ is Martin-Löf random with respect to a
computable measure; see, e.g., [BP12]), $X$ is Martin-Löf random with respect
to a computable measure, and hence $\mathcal{P}$ is not $\mathit{tt}$-deep. ∎

######  Theorem 13.

There is a weakly deep co-c.e. tree $T$ such that $[T]$ is not a
$\mathit{tt}$-deep $\Pi^{0}_{1}$ class.

###### Proof.

The proof is nearly identical to that of Theorem 11. Given any weakly deep
co-c.e. tree $T_{0}$, let $T=0^{\frown}T_{0}\cup 1^{\frown}2^{<\omega}$. Since
$T_{0}\leq_{\mathit{tt}}T$, it follows that $T$ must be weakly deep. However,
$[T]$ contains every Martin-Löf sequence that begins with a 1, it cannot be
$\mathit{tt}$-deep. ∎

Note earlier that we stated the result that being a $\mathit{tt}$-deep
$\Pi^{0}_{1}$ class not only implies that every member of the class is weakly
deep, but also that this latter condition is equivalent to the property of
being $\mathit{tt}$-deep. This equivalence does not hold in the case of deep
$\Pi^{0}_{1}$ classes:

######  Theorem 14.

There is a $\Pi^{0}_{1}$ class $\mathcal{P}$ such that (i) every
$X\in\mathcal{P}$ is strongly deep but (ii) $\mathcal{P}$ is not deep.

###### Proof.

As shown in [BP16, Theorem 4.7], given any deep $\Pi^{0}_{1}$ class
$\mathcal{Q}$, there is a non-deep $\Pi^{0}_{1}$ class $\mathcal{P}$ such that
every member of $\mathcal{P}$ is a finite modification of some member of
$\mathcal{Q}$. By the slow growth law, order-depth is invariant under finite
modifications, so every member of any such class $\mathcal{P}$ is strongly
deep. ∎

###  4.1. Additional examples of deep sequences

Theorem 9 also allows us to derive a number of examples of deep sequences. In
[BP16] it was shown that the following collections of sequences form deep
$\Pi^{0}_{1}$ classes:

  1. (1)

the collection of consistent completions of Peano arithmetic;

  2. (2)

the collection of ($\alpha,c$)-shift-complex sequences for computable
$\alpha\in(0,1)$ and $c\in\omega$, where a sequence $X\in 2^{\omega}$ is
($\alpha,c$)-shift-complex if $K(\tau)\geq\alpha|\tau|-c$ for every substring
$\tau$ of $X$;

  3. (3)

the collection of $\mathrm{DNC}_{q}$ functions with
$\sum_{n\in\omega}\frac{1}{q(n)}=\infty$, where $f:\omega\rightarrow\omega$ is
a $\mathrm{DNC}_{q}$ function if $f$ is total function such that
$f(n)\neq\phi_{n}(n)$ and $f(n)<q(n)$ for all $n\in\omega$;

  4. (4)

the collection of codes of infinite sequences of finite sets
$(F_{0},F_{1},\dotsc)$ of strings of maximal complexity, i.e., there are
computable functions $\ell,f,d:\omega\rightarrow\omega$ such that for all
$n\in\omega$, (i) $|F_{n}|=f(n)$, (ii) $|\sigma|=\ell(n)$ for $\sigma\in
F_{n}$, and (iii) $K(\sigma)\geq\ell(n)-d(n)$ for $\sigma\in F_{n}$; and

  5. (5)

the collection of codes of $K$-compression functions with constant $c$, where
$g:2^{<\omega}\rightarrow\omega$ is a $K$-compression function with constant
$c$ if (i) $g(\sigma)\leq K(\sigma)+c$ for all $\sigma\in 2^{<\omega}$ and
(ii) $\sum_{\sigma\in 2^{<\omega}}2^{-g(\sigma)}\leq 1$.

As an immediate consequence of Theorem 9 and the above results from [BP16], we
have:

######  Corollary 15.

Every sequence in the following collections is strongly deep:

  1. (1)

the collection of consistent completions of Peano arithmetic;

  2. (2)

the collection of shift-complex sequences (i.e., the sequences that are
$(\alpha,c)$-shift complex for some computable $\alpha\in(0,1)$ and
$c\in\omega$);

  3. (3)

the collection of codes of $\mathrm{DNC}_{q}$ functions with
$\sum_{n\in\omega}\frac{1}{q(n)}=\infty$;

  4. (4)

the collection of codes of infinite sequences of finite sets of strings of
maximal complexity; and

  5. (5)

the collection of codes of $K$-compression functions (i.e., $K$-compression
functions with constant $c$ for some $c\in\omega$).

We can obtain further examples of members of deep $\Pi^{0}_{1}$ classes using
a version of the slow growth law for members of deep $\Pi^{0}_{1}$ classes.

######  Lemma 16.

If $X$ is a member of a deep $\Pi^{0}_{1}$ class and $X\leq_{tt}Y$, then $Y$
is a member of a deep $\Pi^{0}_{1}$ class.

###### Proof.

Let $\mathcal{P}$ be a $\Pi^{0}_{1}$ class contain $X$, and let $\Phi$ be a
total Turing functional satisfying $\Phi(Y)=X$. Then by the slow growth law
for deep $\Pi^{0}_{1}$ classes, $\Phi^{-1}(\mathcal{P})$ is a deep
$\Pi^{0}_{1}$ class that contains $Y$, which must be strongly deep by Theorem
9. ∎

######  Theorem 17.

  * (i)

The halting set
$\emptyset^{\prime}=\\{e\in\omega\colon\phi_{e}(e){\downarrow}\\}$ is a member
of a deep $\Pi^{0}_{1}$ class.

  * (ii)

For every $X\in 2^{\omega}$,
$X^{\prime}=\\{e\colon\phi^{X}_{e}(e){\downarrow}\\}$ is a member of a deep
$\Pi^{0}_{1}$ class.

  * (iii)

Every non-trivial index set is a member of a deep $\Pi^{0}_{1}$ class.

###### Proof.

(i) There is a $\mathrm{DNC}_{2}$ function $f$ such that
$f\leq_{tt}\emptyset^{\prime}$ (see [Nie09, Remark 1.8.30]). Since the
collection of $\mathrm{DNC}_{2}$ functions forms a deep $\Pi^{0}_{1}$ class,
the result follows from Lemma 16.
(ii) Since $\emptyset^{\prime}\leq_{tt}X^{\prime}$ for every $X\in 2^{\omega}$
and $\emptyset^{\prime}$ is a member of a deep $\Pi^{0}_{1}$ class by part
(i), the result follows from Lemma 16.
(iii). By Rice’s theorem, every non-trivial index set $C$ satisfies
$\emptyset^{\prime}\leq_{1}C$ or $\overline{\emptyset^{\prime}}\leq_{1}C$, and
so the result follows again from part (i) and Lemma 16.

∎

###  4.2. Separating depth notions

In light of Theorem 9, it is natural to ask whether every order-deep sequence
is a member of a deep $\Pi^{0}_{1}$ class. We show that this does not hold by
establishing several propositions of independent interest.

Recall that a sequence $X$ is complex if there is some computable order $g$
such that $K(X{\upharpoonright}n)\geq g(n)$. As shown explicitly in [HP17],
one can equivalently define a sequence to be complex in terms of a priori
complexity, i.e., $X$ is complex if and only if there is some computable order
$h$ such that $KA(X{\upharpoonright}n)\geq h(n)$. We use this second
characterization to derive the following:

######  Proposition 18.

Every member of a deep $\Pi^{0}_{1}$ class is complex.

###### Proof.

Let $\mathcal{P}$ be a deep $\Pi^{0}_{1}$ class with associated co-c.e. tree
$T$. Then there is some computable order $h:\omega\rightarrow\omega$ such that
$\mathbf{M}(T_{n})\leq 2^{-h(n)}$. Given $X\in\mathcal{P}$, since
$X{\upharpoonright}n\in T_{n}$, we have
$\mathbf{M}(X{\upharpoonright}n)\leq\mathbf{M}(T_{n})\leq 2^{-h(n)}$. Taking
the negative logarithm yields $\mathit{KA}(X{\upharpoonright}n)\geq h(n)$,
from which the conclusion follows. ∎

Next, we have:

######  Proposition 19.

No sequence that is Turing equivalent to an incomplete c.e. set is a member of
a deep $\Pi^{0}_{1}$ class.

###### Proof.

Suppose that $X$ is a member of a deep $\Pi^{0}_{1}$ class and is Turing
equivalent to some incomplete c.e. set $Y$. By Proposition 18, $X$ is complex.
It follows from work of Kjos-Hanssen, Merkle, and Stephan [KHMS11] that $X$
has DNC degree. But then $Y$ is an incomplete c.e. set of DNC degree, which
contradicts Arslanov’s completeness criterion (see, e.g., [Nie09, Theorem
4.1.11]). ∎

######  Theorem 20.

There is an order-deep sequence that is not complex (hence is not a member of
any deep $\Pi^{0}_{1}$ class).

###### Proof.

In [JLL94], Juedes, Lathrop, and Lutz introduced the notion of weakly useful
sequence (we do not recall the definition of this notion here and refer the
reader to their paper) and showed that (i) every weakly useful sequence is
order-deep and (ii) every high degree contains a weakly useful sequence. Our
theorem then follows: Let $X$ be high, incomplete, and weakly useful (hence
order-deep). By the same reasoning in the proof of Proposition 19, $X$ is not
complex. ∎

We note another consequence of Proposition 19, namely that the leftmost path
of every deep $\Pi^{0}_{1}$ class is Turing complete. Indeed, the leftmost
path of a $\Pi^{0}_{1}$ class has c.e. degree and thus must be Turing complete
by Proposition 19.

Having separated order-depth from being a member of a deep $\Pi^{0}_{1}$
class, we can use a similar line of reasoning to further separate order-depth
from Bennett’s original notion of depth. We need one auxiliary result.

######  Theorem 21 (Moser, Stephan [MS17]).

Every order-deep sequence is either high or of DNC degree.

######  Theorem 22.

There is a strongly deep sequence that is not order-deep.

###### Proof.

Downey, MacInerny, and Ng [DMN17] constructed a low, deep sequence $A$ of c.e.
degree. As $A$ can neither be high nor of DNC degree (as it is incomplete), it
follows from Theorem 21 that $A$ is not order-deep. ∎

We have seen by Theorem 9 that members of deep $\Pi^{0}_{1}$ classes are
order-deep, and by Proposition 18 that they are complex. We end this section
by showing that these two properties alone are not enough to characterize
members of deep $\Pi^{0}_{1}$ classes.

######  Theorem 23.

There exists a sequence $X$ which is complex, order-deep, and not a member of
any deep $\Pi^{0}_{1}$ class.

We will need the following auxiliary lemma of independent interest. Recall
that the join $Y\oplus Z$ of two sequences $Y$ and $Z$ is the sequence
obtained by interleaving their bits: $Y\oplus Z=Y(0)Z(0)Y(1)Z(1)\ldots$.
Similarly, for two strings $\sigma$ and $\tau$ of the same length we can
define $\sigma\oplus\tau$ in the same way.

######  Lemma 24.

If a sequence $Y$ is not a member of any deep $\Pi^{0}_{1}$ class, then for
almost every $Z$ (in the sense of Lebesgue measure), $Y\oplus Z$ is not a
member of any deep $\Pi^{0}_{1}$ class.

###### Proof.

We prove this lemma by contrapositive. Suppose that $Y$ is such that for
positive measure many sequences $Z$, $Y\oplus Z$ is a member of a deep
$\Pi^{0}_{1}$ class. If this is so, as there are only countably many deep
$\Pi^{0}_{1}$ classes, this means that there is a fixed deep $\Pi^{0}_{1}$
class $\mathcal{C}$ such that with probability $>\delta$ over $Z$ (with
$\delta$ a positive rational), we have that $Y\oplus Z$ belongs to
$\mathcal{C}$. Consider the $\Pi^{0}_{1}$ class $\mathcal{D}$ consisting of
sequences $A$ such that for any $n$, there are at least $\delta\cdot 2^{n}$
strings $\tau$ such that $(A{\upharpoonright}n)\oplus\tau$ is in the canonical
tree $T$ of $\mathcal{C}$. By definition, $Y$ belongs to $\mathcal{D}$. We
claim that $\mathcal{D}$ is deep, which will prove the lemma. Since
$\mathcal{C}$ is deep, there is a computable order $h$ such that
$\mathbf{M}(T_{2n})<1/h(n)$ for all $n$. Let $P$ be the continuous semimeasure
defined on strings of even length by
$P(\sigma\oplus\tau)=\mathbf{M}(\sigma)\lambda(\tau)$. If $S$ is the canonical
co-c.e. tree of $\mathcal{D}$, then by definition of $\mathcal{D}$, we have

$P(T_{2n})\geq\mathbf{M}(S_{n})\cdot\delta.$

By universality of $\mathbf{M}$, we also have
$\mathcal{P}(T_{2n})\leq^{\times}\mathbf{M}(T_{2n})<1/h(n)$. Putting these two
inequalities together, it follows that

$\mathbf{M}(S_{n})\leq^{\times}\frac{1}{\delta\cdot h(n)}$

which shows $\mathcal{D}$ is a deep $\Pi^{0}_{1}$ class. ∎

###### Proof of Theorem 23.

Having proven Lemma 24, take now $Y$ a sequence that is order-deep and not a
member of any deep $\Pi^{0}_{1}$ class (whose existence was established in
Theorem 20). Pick $Z$ at random and form the sequence $X=Y\oplus Z$. With
probability $1$ over $Z$:

  * •

$X$ is complex. Indeed
$K(X{\upharpoonright}2n)\geq^{+}K(Z{\upharpoonright}n)\geq^{+}n$ by the Levin-
Schnorr theorem.

  * •

$X$ is not a member of any deep $\Pi^{0}_{1}$ class by Lemma 24.

Moreover, regardless of the value of $Z$, $X$ $\mathit{tt}$-computes $Y$ which
is order-deep, hence by the slow growth law for order-deep sequences, $X$ is
itself order-deep. These three properties tell us that with probability $1$
over $Z$, $X=Y\oplus Z$ is as desired.

∎

##  5\. Strong Depth is Negligible

As observed in [BP16] every deep $\Pi^{0}_{1}$ class is negligible. Since the
collection of strongly deep sequences forms a strict superclass of the
collection of members of all deep $\Pi^{0}_{1}$ classes by Theorems 9 and 20,
it is natural to ask whether the collection of strongly deep sequences is
negligible, which we answer in the affirmative.

######  Theorem 25.

The class of strongly deep sequences is negligible.

###### Proof.

For the sake of contradiction, assume there exists a functional $\Phi$ such
that

$\lambda\\{X\ :\ \Phi^{X}\text{~{} is deep ~{}}\\}>0.9$

(where we choose this latter value without loss of generality by the Lebegue
Density Theorem). Let $p$ be a computable semimeasure such that
$\liminf_{n}\frac{\mathbf{m}(n)}{p(n)}<\infty$. The existence of such a $p$
follows from the existence of _Solovay functions_ (see [BDNM15]), which are
functions $f\geq^{+}K$ such that $\liminf_{n}f(n)-K(n)<\infty$. Setting
$p(n)=2^{-f(n)-c}$ with $f$ a Solovay function and $c$ large enough gives us
the properties of $p$ we need.

We now define a computable discrete semimeasure as follows. For every
$n\in\omega$, effectively find a family of clopen sets $\\{C_{\sigma}\ :\
|\sigma|=n\\}$ such that $\Phi^{X}\succeq\sigma$ for all $X\in C_{\sigma}$ and
$\sum_{|\sigma|=n}\lambda(C_{\sigma})>0.9$. Then, set for all $\sigma$ of
length $n$:

$q(\sigma)=\lambda(C_{\sigma})\cdot p(n)$

It is clear that $q$ is computable. Moveover, $q$ is a discrete semimeasure,
since

$\sum_{\sigma\in
2^{<\omega}}q(\sigma)=\sum_{n\in\omega}\sum_{|\sigma|=n}\lambda(C_{\sigma})\cdot
p(n)=\sum_{n\in\omega}p(n)\sum_{\sigma\in
2^{<\omega}\colon|\sigma|=n}\lambda(C_{\sigma})\leq\sum_{n\in\omega}p(n)\leq
1.$

For any $Y$ that is strongly deep, we must have
$\frac{\mathbf{m}(Y{\upharpoonright}n)}{q(Y{\upharpoonright}n)}\rightarrow\infty$.
For all $(n,d)$, define

$B^{d}_{n}=\\{\sigma\ :\ |\sigma|=n~{}\text{~{} ~{} and ~{} ~{}
}~{}\mathbf{m}(\sigma)>d\cdot q(\sigma)\\}$

By our hypothesis on the functional $\Phi$, this means that for every constant
$d$, for almost all $n$, $\lambda(\\{X\ :\ \Phi^{X}{\upharpoonright}n\in
B^{d}_{n}\\})>0.9$.

Now, consider the quantity $\sum_{\sigma\in B^{d}_{n}}\lambda(C_{\sigma})$. On
the one hand,

$\displaystyle\sum_{\sigma\in B^{d}_{n}}\lambda(C_{\sigma})$
$\displaystyle=\sum_{\sigma\in B^{d}_{n}}\frac{q(\sigma)}{p(n)}\hskip
28.45274pt\text{(by definition of $q$)}$ $\displaystyle\leq\sum_{\sigma\in
B^{d}_{n}}\frac{\mathbf{m}(\sigma)}{d\cdot p(n)}\hskip 28.45274pt\text{(by
definition of $B^{d}_{n}$)}$ $\displaystyle\leq\frac{1}{d\cdot
p(n)}\sum_{|\sigma|=n}\mathbf{m}(\sigma)$
$\displaystyle\leq\frac{\mathbf{m}(n)\cdot O(1)}{d\cdot p(n)}\hskip
28.45274pt\text{(using the identity
$\sum_{|\sigma|=n}\mathbf{m}(\sigma)=^{\times}\mathbf{m}(n)$)}$

On the other hand, for almost all $n$:

$\displaystyle\sum_{\sigma\in B^{d}_{n}}\lambda(C_{\sigma})$
$\displaystyle\geq\lambda(\\{X\ :\ \Phi^{X}{\upharpoonright}n\in
B^{d}_{n}\\})-0.1\hskip 28.45274pt\text{(because
$\lambda(\bigcup_{|\sigma|=n}C_{\sigma})>0.9$)}$ $\displaystyle\geq 0.9-0.1$
$\displaystyle\geq 0.8$

Putting the two together, we have established that for all $d$, for almost all
$n$, $\frac{\mathbf{m}(n)}{p(n)}>d/O(1)$, i.e.,
$\lim_{n}\frac{\mathbf{m}(n)}{p(n)}=\infty$. This contradicts the choice of
$p$. ∎

Note, by contrast, that the collection of weakly deep sequences is not
negligible. Indeed, as shown by Muchnik et al. [MSU98], no 1-generic sequence
is Martin-Löf random with respect to a computable measure, and thus every
1-generic is weakly deep. Moreover, as shown by Kautz [Kau91], every 2-random
sequence computes a 1-generic, and hence the collection of 1-generics is not
negligible.

As the collection of strongly deep sequences is negligible, it is worth asking
whether the collection of sequences that are strongly deep with respect to one
fixed computable time bound is negligible. We first introduce some notation.
For a computable time bound $t$ and $c\in\omega$, let $D^{t}_{c}(n)=\\{X\in
2^{\omega}\colon K^{t}(X{\upharpoonright}n)-K(X{\upharpoonright}n)\geq c\\}$,
which is clopen uniformly in $n$, hence $\bigcap_{n\geq m}D^{t}_{c}(n)$ is a
$\Pi^{0}_{1}$ class. In addition, we set
$D^{t}_{c}=\bigcup_{m\in\omega}\bigcap_{n\geq m}D^{t}_{c}(n)$. Then we have:

######  Theorem 26.

Let $t$ be a computable time bound and $c\in\omega$. Then $D^{t}_{c}$ is not
negligible and hence does not consist entirely of strongly deep sequences.

###### Proof.

Suppose on the contrary that $D^{t}_{c}$ is negligible for some computable
time bound $t$ and $c\in\omega$. Then for each $m\in\omega$, $\bigcap_{n\geq
m}D^{t}_{c}(n)$ is a negligible $\Pi^{0}_{1}$ class. As shown in [BP16,
Theorem 5.2], no weakly 2-random sequence can compute a member of a negligible
$\Pi^{0}_{1}$ class, hence no weakly 2-random sequence can compute a member of
$\bigcap_{n\geq m}D^{t}_{c}(n)$ (recall that $X\in 2^{\omega}$ is weakly
2-random if $X$ is not contained in any $\Pi^{0}_{2}$ of Lebesgue measure
zero). It follows that no weakly 2-random sequence can compute a member of
$D^{t}_{c}$. However, there is some weakly 2-random sequence that computes a
sequence of high Turing degree [Kau91], and as shown by Juedes, Lathrop, and
Lutz [JLL94], every high degree contains a strongly deep sequence. In
particular, every high degree contains an element of $D^{t}_{c}$, and thus
there is some weakly 2-random sequence that computes a member of $D^{t}_{c}$,
a contradiction. Note further that under the assumption that $D^{t}_{c}$
consists entirely of strongly deep sequences, then by Theorem 25, it would
follow that $D^{t}_{c}$ is negligible, which we have shown cannot hold. ∎

##  6\. Variants of Strong Depth

###  6.1. Depth via continuous semimeasures

In [BP16], the authors show that the definition of a deep $\Pi^{0}_{1}$ class
can be equivalently defined simply by replacing the universal continuous
semimeasure $\mathbf{M}$ with the universal discrete semimeasure $\mathbf{m}$:
a $\Pi^{0}_{1}$ class $\mathcal{P}$ with canonical co-c.e. tree $T$ is deep if
and only if there is a computable order $h$ such that
$\mathbf{m}(T_{n})<2^{-h(n)}$ for all $n\in\omega$, if and only if there is a
computable order $f$ such that $\mathbf{m}(T_{f(n)})<2^{-n}$ for all
$n\in\omega$. Given the characterization of deep sequences in terms of
discrete semimeasures in Section 3, it is natural to ask whether we can
equivalently characterize strong depth by replacing the discrete semimeasures
in the definition with continuous semimeasures. We show that, in this case, we
only obtain a characterization of weak depth.

######  Theorem 27.

$X\in 2^{\omega}$ is weakly deep if and only if for every computable
continuous semimeasure $P$,

$\frac{\mathbf{M}(X{\upharpoonright}n)}{P(X{\upharpoonright}n)}\rightarrow\infty.$

###### Proof.

Suppose that $X$ is not weakly deep. Then there is some computable measure
$\mu$ such that $X$ is $\mu$-Martin-Löf random. By the Levin-Schnorr theorem
for a priori complexity with respect to the measure $\mu$ (implicit in
[Lev73]), there is some $c$ such that

$\mathit{KA}(X{\upharpoonright}n)\geq-\log\mu(X{\upharpoonright}n)-c$

for all $n\in\omega$. Equivalently, we have

$\mathbf{M}(X{\upharpoonright}n)\leq 2^{c}\cdot\mu(X{\upharpoonright}n)$

Since every computable measure is a computable semimeasure, the conclusion
follows.

For the other direction, suppose that there is some computable, continuous
semimeasure and some $c\in\omega$ such that for all $n\in\omega$,

(1) $\frac{\mathbf{M}(X{\upharpoonright}n)}{P(X{\upharpoonright}n)}<c.$

From $P$, we can define a computable measure $\mu$ as follows. First, we
define a function $g:2^{<\omega}\rightarrow 2^{<\omega}$ by setting

$g(\sigma)=P(\sigma)-(P(\sigma 0)+P(\sigma 1))$

for every $\sigma\in 2^{<\omega}$. Clearly $g$ is computable since $P$ is.
Next we define a computable measure $\mu$ on $2^{\omega}$ by setting

$\mu(\sigma)=P(\sigma)+\sum_{\tau\prec\sigma}2^{|\tau|-|\sigma|}g(\tau).$

One can readily verify that $\mu$ is a measure (see the proof of Proposition
3.5 in [BHPS14]) and $P(\sigma)\leq\mu(\sigma)$ for all $\sigma\in
2^{<\omega}$. From Equation (1) we can derive

$\mathit{KA}(X{\upharpoonright}n)\geq-\log
P(X{\upharpoonright}n)-O(1)\geq-\log\mu(X{\upharpoonright}n)-O(1).$

It thus follows from the Levin-Schnorr theorem for a priori complexity that
$X$ is $\mu$-Martin-Löf random and hence is not weakly deep. ∎

We define a sequence to be _$\mathit{KA}$ -deep_ if

$\mathit{KA}^{t}(X{\upharpoonright}n)-\mathit{KA}(X{\upharpoonright}n)\rightarrow\infty$

where $\mathit{KA}^{t}:=-\log\mathbf{M}^{t}$ as discussed in Section 2.3.
Recall further from Section 2.3 that for every computable continuous
semimeasure $P$, there is some computable time bound $t$ such that
$P\leq^{\times}\mathbf{M}^{t}$. It is thus straightforward to show that for
$X\in 2^{\omega}$ and every computable continuous semimeasure $P$,

$\frac{\mathbf{M}(X{\upharpoonright}n)}{P(X{\upharpoonright}n)}\rightarrow\infty$

if and only if for every computable time bound $t$,

$\frac{\mathbf{M}(X{\upharpoonright}n)}{\mathbf{M}^{t}(X{\upharpoonright}n)}\rightarrow\infty$

(see the proof of [BDM23, Lemma 2.6] for discrete semimeasures which directly
translates to the case of continuous semimeasures). Thus we can conclude:

######  Corollary 28.

$X\in 2^{\omega}$ is $\mathit{KA}$-deep if and only if $X$ is weakly deep.

###  6.2. Depth and monotone complexity

We can obtain a similar characterization of weak depth in terms of monotone
complexity. Define a sequence to be _$\mathit{Km}$ -deep_ if

$\mathit{Km}^{t}(X{\upharpoonright}n)-\mathit{Km}(X{\upharpoonright}n)\rightarrow\infty$

This notion was studied by Schnorr and Fuchs [SF77], who used the term
_superlearnable_ to refer to the failure of being $\mathit{Km}$-deep. In
particular, Schnorr and Fuchs proved that a sequence is superlearnable if and
only if it is Martin-Löf random with respect to a computable measure. Given
that a sequence is weakly deep if and only if it is not Martin-Löf random with
respect to a computable measure, we have the following.

######  Theorem 29.

$X\in 2^{\omega}$ is $\mathit{Km}$-deep if and only if $X$ is weakly deep.

## References

  * [BDM23] Laurent Bienvenu, Valentino Delle Rose, and Wolfgang Merkle.  Relativized depth.  Theoretical Computer Science, 949:113694, 2023.
  * [BDNM15] Laurent Bienvenu, Rodney G. Downey, André Nies, and Wolfgang Merkle.  Solovay functions and their applications in algorithmic randomness.  Journal of Computer and System Sciences, 81(8):1575–1591, 2015\.
  * [Ben95] Charles H. Bennett.  Logical depth and physical complexity.  In The Universal Turing Machine A Half-Century Survey, pages 207–235. Springer, 1995.
  * [BHPS14] Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter, and Paul Shafer.  Randomness and semi-measures.  preprint, arXiv:1310.5133, 2014.
  * [BP12] Laurent Bienvenu and Christopher P. Porter.  Strong reductions in effective randomness.  Theoretical Computer Science, 459:55–68, 2012.
  * [BP16] Laurent Bienvenu and Christopher P Porter.  Deep classes.  Bulletin of Symbolic Logic, 22(2):249–286, 2016.
  * [DMN17] Rod Downey, Michael McInerney, and Keng Meng Ng.  Lowness and logical depth.  Theoretical Computer Science, 702:23–33, 2017.
  * [HP17] Rupert Hölzl and Christopher P Porter.  Randomness for computable measures and initial segment complexity.  Annals of Pure and Applied Logic, 168(4):860–886, 2017.
  * [JLL94] David W Juedes, James I Lathrop, and Jack H Lutz.  Computational depth and reducibility.  Theoretical Computer Science, 132(1-2):37–70, 1994.
  * [Kau91] Steven M. Kautz.  Degrees of random sequences.  PhD thesis, Cornell University, 1991.
  * [KHMS11] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan.  Kolmogorov complexity and the recursion theorem.  Transactions of the American Mathematical Society, 363(10):5465–5480, 2011.
  * [Lev73] Leonid A Levin.  On the notion of a random sequence.  In Soviet. Math. Dokl., volume 14, pages 1413–1416, 1973.
  * [Lev84] Leonid Levin.  Randomness conservation inequalities; information and independence in mathematical theories.  Information and Control, 61:15–37, 1984.
  * [Lev13] Leonid Levin.  Forbidden information.  Journal of the ACM, 60(2):9, 2013.
  * [LZ70] L. A. Levin and A. K. Zvonkin.  The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms.  Uspehi Mat. Nauk, 25(6(156)):85–127, 1970.
  * [MS17] Philippe Moser and Frank Stephan.  Depth, highness and dnr degrees.  Discrete Mathematics & Theoretical Computer Science, 19(special issue FCT’15), 2017.
  * [MSU98] Andrei A Muchnik, Alexei L Semenov, and Vladimir A Uspensky.  Mathematical metaphysics of randomness.  Theoretical Computer Science, 207(2):263–317, 1998.
  * [Nie09] André Nies.  Computability and randomness, volume 51.  Oxford University Press, 2009.
  * [SF77] Claus-Peter Schnorr and P Fuchs.  General random sequences and learnable sequences.  The Journal of Symbolic Logic, 42(3):329–340, 1977.

##  Appendix A Proof of Lemma 3

Working towards the proof of Lemma 3, we first establish the following result.

######  Lemma 30.

Let $E$ be a computable function which maps every string to a finite set of
strings. For every time bound $t$, there exists a time bound $s$ such that for
every $\sigma\in 2^{<\omega}$ and every $\tau\in E(\sigma)$:

$K^{s}(\sigma)+K^{s}(\tau\mid\sigma)\leq^{+}K^{t}(\sigma,\tau).$

###### Proof.

Given the computable time bound $t$, $t^{\prime}$ be a computable time bound
such that $2^{-K^{t}}\leq^{\times}\mathbf{m}^{t^{\prime}}$ as guaranteed by
Lemma 1(iii). Let $p$ be the conditional discrete semimeasure defined by

$p(\tau\mid\sigma)=\frac{\mathbf{m}^{t^{\prime}}(\sigma,\tau)}{\sum_{\rho\in
E(\sigma)}\mathbf{m}^{t^{\prime}}(\sigma,\rho)}$

when $\tau\in E(\sigma)$ and $p(\tau\mid\sigma)=0$ otherwise (note that a
conditional discrete semimeasure $p(\cdot\mid\cdot)$ must satisfy the
condition that $p(\cdot\mid\sigma)$ is a discrete semimeasure for each
$\sigma\in 2^{<\omega}$). It is clear that $p$ is indeed a conditional
discrete semimeasure and that it is computable. The denominator in this
expression $q(\sigma):={\sum_{\rho\in
E(\sigma)}\mathbf{m}^{t^{\prime}}(\sigma,\rho)}$ is also a computable discrete
semimeasure since
$\sum_{\sigma}q(\sigma)\leq\sum_{\sigma}\sum_{\rho}\mathbf{m}^{t^{\prime}}(\sigma,\rho)\leq\sum_{\sigma}\sum_{\rho}\mathbf{m}(\sigma,\rho)\leq
1$.

We thus have the identity

$\mathbf{m}^{t^{\prime}}(\sigma,\tau)=p(\tau\mid\sigma)\cdot q(\sigma)$

with $p,q$ computable discrete semimeasures. By Lemma 1, there is a computable
time bound $s^{\prime}$ such that $p,q\leq\mathbf{m}^{s}$ and thus

$\mathbf{m}^{t^{\prime}}(\sigma,\tau)\leq\mathbf{m}^{s^{\prime}}(\tau\mid\sigma)\cdot\mathbf{m}^{s^{\prime}}(\sigma).$

Then by our initial assumption on $t$ and $t^{\prime}$, we have

$2^{-K^{t}(\sigma,\tau)}\leq^{\times}\mathbf{m}^{s^{\prime}}(\tau\mid\sigma)\cdot\mathbf{m}^{s^{\prime}}(\sigma).$

Finally, by Theorem 2, as there is a computable time bound $s$ such that
$\mathbf{m}^{s^{\prime}}\leq^{\times}2^{-K^{s}}$, we have

$2^{-K^{t}(\sigma,\tau)}\leq^{\times}2^{-K^{s}(\tau\mid\sigma)}\cdot
2^{-K^{s}(\sigma)}.$

The lemma follows by taking the negative logarithm of this inequality. ∎

We can now prove Lemma 3. The (i)$\rightarrow$(ii) implication is immediate.
For the (ii)$\rightarrow$(i) implication, suppose $X$ is a sequence and $h$ a
computable increasing function such that

$K^{t}(X{\upharpoonright}h(n))-K(X{\upharpoonright}h(n))\geq^{+}n$

for any time bound $t$. If $k\in[h(n),h(n+1))$, we have

(2)
$K(X{\upharpoonright}k)\leq^{+}K(X{\upharpoonright}h(n))+K(X{\upharpoonright}[h(n),k)\mid
X{\upharpoonright}h(n)).$

We now apply the previous lemma with $\sigma=X{\upharpoonright}h(n)$,
$\tau=X{\upharpoonright}[h(n),k)$ and $E$ the map such that, on input $\rho$,
checks whether $\rho$ has length $h(n)$ for some $n$ and if so returns all
strings whose length is between $0$ and $h(n+1)-h(n)$ (otherwise $E(\rho)$ is
empty). The lemma gives us a computable time bound $s$ such that

(3)
$K^{s}(X{\upharpoonright}h(n))+K^{s}(X{\upharpoonright}[h(n),k)|X{\upharpoonright}h(n))\leq^{+}K^{t}(X{\upharpoonright}k).$

Putting (2) and (3) together, and using the fact that
$K(X{\upharpoonright}[h(n),k)\mid X{\upharpoonright}h(n))\leq
K^{s}(X{\upharpoonright}[h(n),k)\mid X{\upharpoonright}h(n))$, it follows
that:

(4)
$K^{t}(X{\upharpoonright}k)-K(X{\upharpoonright}k)\geq^{+}K^{s}(X{\upharpoonright}h(n))-K(X{\upharpoonright}h(n))\geq^{+}n.$

This being true for all $n$ and all $k\in[h(n),h(n+1))$, we have

(5) $K^{t}(X{\upharpoonright}k)-K(X{\upharpoonright}k)\geq^{+}h^{-1}(k),$

and thus $X$ is order-deep.

Finally, the (ii)$\leftrightarrow$(iii) equivalence can be established using
Lemma 1(iii) and Theorem 2.