######  Remark V.3.5.

The negligibility of $\mathrm{SC}$ implies that there are $X$ which are
$\lambda n.\sqrt{n}$-shift complex which are not $\delta$-shift complex for
any $\delta\in(0,1)$.

######  Remark V.3.6.

In the proof of Theorem V.3.3, at Stage $s+1$ we encode
$X{\upharpoonright}\,b_{s+1}2^{m_{0}+s+1}$ even though
$X{\upharpoonright}\,b_{s}2^{m_{0}+s}$ has already been encoded, so that in a
certain sense we continually retread old ground. A more conservative approach
would be to encode
$X{\upharpoonright}\,[b_{0}2^{m_{0}}+b_{1}2^{m_{0}+1}+\@cdots+b_{s}2^{m_{0}+s},b_{0}2^{m_{0}}+b_{1}2^{m_{0}+1}+\@cdots+b_{s}2^{m_{0}+s}+b_{s+1}2^{m_{0}+s+1})$
at Stage $s+1$, so that for some $c\in\mathbb{N}$ and all $k,m\in\mathbb{N}$,

$\displaystyle\operatorname{KP}(\Psi(X)({[k,k+2^{m})}))$ $\displaystyle\geq
a_{0}2^{m_{0}}+a_{1}2^{m_{0}+1}+\@cdots+a_{m}2^{m}-c,$
$\displaystyle\geq\left(\frac{a_{0}}{2^{m-m_{0}}}+\frac{a_{1}}{2^{m-m_{0}-1}}+\@cdots+\frac{a_{m}}{2^{0}}\right)2^{m}-c.$

Let
$c_{m}=\left(\frac{a_{0}}{2^{m-m_{0}}}+\frac{a_{1}}{2^{m-m_{0}-1}}+\@cdots+\frac{a_{m}}{2^{0}}\right)$,
defined for $m\geq m_{0}$. Then

$\displaystyle\tsum\slimits@_{k=0}^{m-m_{0}}{c_{m_{0}+k}}$
$\displaystyle=c_{m_{0}}+c_{m_{0}+1}+\@cdots+c_{m}$
$\displaystyle=a_{0}+\left(\frac{a_{0}}{2}+a_{1}\right)+\left(\frac{a_{0}}{4}+\frac{a_{1}}{2}+a_{2}\right)+\@cdots+\left(\frac{a_{0}}{2^{m-m_{0}}}+\frac{a_{1}}{2^{m-m_{0}-1}}+\@cdots+a_{m}\right)$
$\displaystyle=\tsum\slimits@_{k=0}^{m}{\left(2-\frac{1}{2^{m-m_{0}+1-k}}\right)a_{k}}$

It follows that $\tsum\slimits@_{k=0}{c_{m_{0}+k}}$ converges. In particular,
this ‘conservative’ approach does not produce any stronger general conclusion.

####  V.3.1 Relating Generalized Shift Complexity and Complexity

The total recursive functional $\Psi$ defined in the proof of Theorem V.3.3
can be used to provide stronger results about the location of
$\mathop{\deg_{\mathrm{w}}}(\mathrm{SC}(f))$ in $\mathcal{E}_{\mathrm{w}}$ for
order functions $f$ satisfying
$\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}<\infty$.

######  Theorem V.3.7.

Suppose $f,g\colon\mathbb{N}\to{[0,\infty)}$ are sub-identical order functions
such that $\tsum\slimits@_{m=0}{f(2^{m})/2^{m}}<\infty$ and for which there is
a recursive sequence $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ of
positive rationals such that $\tsum\slimits@_{m=0}{\varepsilon_{m}}<\infty$
and

$\liminf_{m}{\frac{g(2^{m}\varepsilon_{m})-f(2\cdot 2^{m})}{m}}>1.$

Then $\mathrm{SC}(f)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(g)$.

###### Proof.

Suppose $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ satisfies the
hypotheses of the theorem. Let $\alpha$ be a rational number such that
$1<\alpha<\liminf_{m}{\frac{g(2^{m}\varepsilon_{m})-f(2\cdot 2^{m})}{m}}$, so
that $g(2^{m}\varepsilon_{m})-\alpha m\geq f(2\cdot 2^{m})$ for almost all
$m\in\mathbb{N}$.

Now define $\Psi$ as in the proof of Theorem V.3.3, using $\langle
a_{m}\rangle_{m\in\mathbb{N}}=\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$.
As in that proof, there is a $c_{1}$ such that for all $k\in\mathbb{N}$ and
$m\geq m_{0}$, we have

$\operatorname{KP}(\Psi(X)({[k,k+2^{m})}))+\operatorname{KP}(k\bmod
2^{m})+\operatorname{KP}(m)\geq\operatorname{KP}(X{\upharpoonright}\,2^{m}\varepsilon_{m})-c_{1}.$

If $X\in\mathrm{COMPLEX}(g)$, then there is a $c_{2}$ such that
$\operatorname{KP}(X{\upharpoonright}\,2^{m}\varepsilon_{m})\geq
g(2^{m}\varepsilon_{m})-c_{2}$ for all $m\in\mathbb{N}$. Consequently, for all
$k,m\in\mathbb{N}$ we have

$\operatorname{KP}(\Psi(X)({[k,k+2^{m})}))+\operatorname{KP}(k\bmod
2^{m})+\operatorname{KP}(m)\geq g(2^{m}\varepsilon_{m})-(c_{1}+c_{2}).$

Additionally, noting that $1<\frac{1+\alpha}{2}$, there are
$c_{3},c_{4}\in\mathbb{N}$ such that

$\displaystyle\operatorname{KP}(k\bmod 2^{m})$ $\displaystyle\leq\max_{0\leq
k<2^{m}}{\operatorname{KP}(k)}\leq(\tfrac{1+\alpha}{2})m+c_{3},$
$\displaystyle\operatorname{KP}(m)$ $\displaystyle\leq 2\log_{2}m+c_{4},$

for all $m\in\mathbb{N}$, so that for all $k,m\in\mathbb{N}$ we have

$\operatorname{KP}(\Psi(X)({[k,k+2^{m})}))\geq
g(2^{m}\varepsilon_{m})-\left((\tfrac{1+\alpha}{2})\cdot
m-2\log_{2}m\right)-(c_{1}+c_{2}+c_{3}+c_{4}).$

For sufficiently large $m$, $(\frac{1+\alpha}{2})\cdot m+2\log_{2}m\leq\alpha
m$, and hence $\alpha m-\left((\frac{1+\alpha}{2})m-2\log_{2}m\right)$ is
bounded from below, say by $c_{5}$. Let $c=c_{1}+c_{2}+c_{3}+c_{4}+c_{5}$.
Then for all $k$ and all $m\in\mathbb{N}$,

$\operatorname{KP}(\Psi(X)({[k,k+2^{m})}))\geq f(2\cdot 2^{m})-c\geq
f(2^{m})-c.$

In other words, if $\tau$ is a substring of $\Psi(X)$ whose length $|\tau|$ is
a power of $2$, then

$\operatorname{KP}(\tau)\geq f(2\cdot|\tau|)-c\geq f(|\tau|)-c.$ ()

Now suppose $\tau$ is an arbitrary substring of $\Psi(X)$. Let $\tau^{\prime}$
be the longest initial segment of $\tau$ whose length is a power of $2$, say
$2^{m}$. Let $n=|\tau|$. Note that $\lfloor\log_{2}n\rfloor=m$ and $n\leq
2^{m+1}$. Because $\tau^{\prime}$ can be found recursively from $\tau$, that
$f$ is monotonic, and using () ‣ V.3.1, there is a $c_{6}\in\mathbb{N}$
independent of $\tau$ such that

$\operatorname{KP}(\tau)\geq\operatorname{KP}(\tau^{\prime})-c_{6}\geq
f(2\cdot|\tau^{\prime}|)-(c+c_{6})=f(2^{m+1})-(c+c_{6})\geq f(n)-(c+c_{6}).$

∎

######  Remark V.3.8.

The requirement that $\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}$ converges
is necessary for Theorem V.3.7 to yield any useful information – the existence
of a convergent series $\tsum\slimits@_{m=0}{\varepsilon_{m}}$ such that
$2^{m}\varepsilon_{m}-f(2^{m+1})\geq 0$ (so $g$ is the identity function)
implies $\tsum\slimits@_{m=0}{\frac{f(2^{m+1})}{2^{m}}}$ converges, which is
equivalent to the convergence of
$\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}=f(1)+\frac{1}{2}\tsum\slimits@_{m=0}{\frac{f(2^{m+1})}{2^{m}}}$.

Despite the technicality of the condition in Theorem V.3.7, we can deduce
several nice relationships:

######  Corollary V.3.9.

Suppose $f\colon\mathbb{N}\to{[0,\infty)}$ is a sub-identical order function
such that $\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}$ converges. Then for
every rational $\delta\in(0,1]$,
$\mathrm{SC}(f)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\delta)$.

###### Proof.

Define $g$ by setting $g(n)\mathrel{{\vdotdot}{\equal}}\delta n$ for
$n\in\mathbb{N}$ and define $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$
by setting
$\varepsilon_{m}\mathrel{{\vdotdot}{\equal}}\frac{1}{\delta}\left(\frac{f(2^{m+1})}{2^{m}}+\frac{m^{2}}{2^{m}}\right)$
for $m\in\mathbb{N}$. Then

$\displaystyle\lim_{m\to\infty}{\frac{g(2^{m}\varepsilon_{m})-f(2^{m+1})}{m}}$
$\displaystyle=\lim_{m\to\infty}{\frac{f(2^{m+1})+m^{2}-f(2^{m+1})}{m}}$
$\displaystyle=\lim_{m\to\infty}{m}$ $\displaystyle=\infty$ $\displaystyle>1,$

so Theorem V.3.7 shows
$\mathrm{COMPLEX}(\alpha)=\mathrm{COMPLEX}(g)\mathrel{{}_{\mathrm{s}}}\mathrm{SC}(f)$.
∎

######  Corollary V.3.10.

Suppose $0<\alpha<\beta\leq 1$ are rational numbers. Then $\mathrm{SC}(\lambda
n.n^{\alpha})\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda n.n^{\beta})$.

###### Proof.

Define $f$, $g$, and $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ by
setting $f(n)\mathrel{{\vdotdot}{\equal}}n^{\alpha}$,
$g(n)\mathrel{{\vdotdot}{\equal}}n^{\beta}$, and
$\varepsilon_{m}\mathrel{{\vdotdot}{\equal}}m^{-1/\beta}$ for each
$n,m\in\mathbb{N}$. Then
$\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}=\tsum\slimits@_{m=0}{\frac{1}{m^{\beta}}}<\infty$
and

$\displaystyle\lim_{m\to\infty}{\frac{g(2^{m}\varepsilon_{m})-f(2^{m+1})}{m}}$
$\displaystyle=\lim_{m\to\infty}{2^{\beta\cdot m}/m-2^{\alpha\cdot m}}{m}$
$\displaystyle=\lim_{m\to\infty}{\frac{2^{\beta\cdot m}-2^{\alpha\cdot
m}m^{2}}{m^{2}}}$ $\displaystyle=\infty$ $\displaystyle>1,$

so Theorem V.3.7 shows $\mathrm{SC}(\lambda
n.n^{\alpha})\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda n.n^{\beta})$.
∎

######  Corollary V.3.11.

Suppose $0<\alpha+1<\beta$ and rational numbers. Then

$\mathrm{SC}(\lambda
n.n/(\log_{2}n)^{\beta})\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda
n.n/(\log_{2}n)^{\alpha}).$

###### Proof.

Define $f$, $g$, and $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ by
setting $f(n)\mathrel{{\vdotdot}{\equal}}n/(\log_{2}n)^{\beta}$,
$g(n)\mathrel{{\vdotdot}{\equal}}n/(\log_{2}n)^{\alpha}$, and
$\varepsilon_{m}\mathrel{{\vdotdot}{\equal}}1/m(\log_{2}m)^{2}$ for each
$m,n\in\mathbb{N}$. Then

$\displaystyle\lim_{m\to\infty}{\frac{g(2^{m}\varepsilon_{m})-f(2^{m+1})}{m}}$
$\displaystyle=\lim_{m\to\infty}{\frac{1}{m}\left(\frac{2^{m}m^{-1}(\log_{2}m)^{-2}}{(\log_{2}(2^{m}m^{-1}(\log_{2}m)^{-2}))^{\alpha}}-\frac{2^{m+1}}{m^{\beta}}\right)}$
$\displaystyle=\lim_{m\to\infty}{2^{m}\left(\frac{1}{m^{\alpha+2}(1-(\log_{2}m)/m-2(\log_{2}\log_{2}m)/m)^{\alpha}(\log_{2}m)^{2}}-\frac{2}{m^{\beta+1}}\right)}$
$\displaystyle=\infty$ $\displaystyle>1,$

so Theorem V.3.7 shows $\mathrm{SC}(\lambda
n.n/(\log_{2}n)^{\beta})\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda
n.n/(\log_{2}n)^{\alpha})$. ∎

####  V.3.2 Extracting Generalized Shift Complexity from Sublinear Complexity

Corollaries V.3.10, LABEL: and V.3.11 show for certain sufficiently slow-
growing and well-behaved order functions $f$ there is another order function
$g$ such that $\mathrm{COMPLEX}(g)\mathrel{{}_{\mathrm{s}}}\mathrm{SC}(f)$
which is sublinear. We can show that this holds more generally given that
$\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}$ not only converges, but
converges to a recursive real.

######  Theorem V.3.12.

Suppose $f\colon\mathbb{N}\to{[0,\infty)}$ is a sub-identical order function
such that $\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}$ converges to a
recursive real. Then there is a sublinear order function
$g\colon\mathbb{N}\to{[0,\infty)}$ such that
$\mathrm{SC}(f)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(g)$.

To prove Theorem V.3.12, we start by making several observations concerning
recursive series of positive rational numbers.

######  Lemma V.3.13.

Suppose $\langle\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ is a recursive
sequence of positive rational numbers such that
$\tsum\slimits@_{m=0}{\varepsilon_{m}}$ converges to a recursive real. Then
there exists a nondecreasing, recursive sequence
$\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$ of positive integers such that
$\tsum\slimits@_{m=0}{\varepsilon_{m}\gamma_{m}}$ converges to a recursive
real and $\lim_{m\to\infty}{\gamma_{m}}=\infty$.

###### Proof.

Let
$\varepsilon\mathrel{{\vdotdot}{\equal}}\tsum\slimits@_{m=0}{\varepsilon_{m}}$,
which is a recursive real by hypothesis. Recursively define a strictly
increasing sequence $\langle n_{k}\rangle_{k\in\mathbb{N}}$ by setting
$n_{0}\mathrel{{\vdotdot}{\equal}}0$ and, given $n_{k}$ has been defined, let
$n_{k+1}$ be the largest $n>n_{k}$ such that
$\tsum\slimits@_{m=n_{k}+1}^{n}{\varepsilon_{m}}\leq\frac{\varepsilon}{2^{k+1}}$.
Note, then, that
$\tsum\slimits@_{m=n_{k}+1}^{n}{(k+1)\varepsilon_{m}}\leq\frac{(k+1)\varepsilon}{2^{k+1}}$.

We define sequences of positive integers
$\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$ and
$\langle\delta_{m}\rangle_{m\in\mathbb{N}}$ recursively. Start by setting
$\gamma_{m}\mathrel{{\vdotdot}{\equal}}\delta_{m}=1$ for $0=n_{0}\leq
m<n_{1}$, let $\gamma_{n_{1}}\mathrel{{\vdotdot}{\equal}}1$, and let
$\delta_{n_{1}}$ be the largest integer such that
$\tsum\slimits@_{m=n_{0}}^{n_{1}}{\varepsilon_{m}\delta_{m}}\leq\varepsilon/2$
– because $\tsum\slimits@_{m=n_{0}}^{n_{1}}{\varepsilon_{m}}\leq\varepsilon/2$
by our definition of $n_{1}$, we know $\delta_{n_{1}}\geq 1$. Analogously,
given $\gamma_{m}$ and $\delta_{m}$ have been defined for $m\leq n_{k}$, let
$\gamma_{m}\mathrel{{\vdotdot}{\equal}}\delta_{m}\mathrel{{\vdotdot}{\equal}}k+1$
for $n_{k}+1\leq m<n_{k+1}$, let $\gamma_{n_{k+1}}=k+1$, and let
$\delta_{n_{k+1}}$ be the largest integer such that
$\tsum\slimits@_{m=0}^{n_{k+1}}{\varepsilon_{m}\delta_{m}}\leq\tsum\slimits@_{j=1}^{k+1}{\frac{j}{2^{j}}}$
– because
$\tsum\slimits@_{m=n_{k}+1}^{n}{(k+1)\varepsilon_{m}}\leq\frac{(k+1)\varepsilon}{2^{k+1}}$
by our definition of $n_{k+1}$, it follows that $\delta_{n_{k+1}}\geq k+1$.

By construction, $\tsum\slimits@_{m=0}{\varepsilon_{m}\delta_{m}}$ converges
to the recursive real
$\tsum\slimits@_{k=1}{\frac{k\varepsilon}{2^{k}}}=2\varepsilon$ (here, we use
the fact that $\lim_{k\to\infty}{\varepsilon_{n_{k}}}=0$ so that the
difference
$\tsum\slimits@_{j=1}^{k+1}{\frac{j}{2^{j}}}-\tsum\slimits@_{m=0}^{n_{k+1}}{\varepsilon_{m}\delta_{m}}$
is made arbitrarily small as $k\to\infty$). Because $\varepsilon$ is a
recursive real, the above construction is also recursive, so the sequences
$\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$ and
$\langle\delta_{m}\rangle_{m\in\mathbb{N}}$ are recursive. As observed above,
$\gamma_{m},\delta_{m}\geq k+1$ for $n_{k}+1\leq m\leq n_{k+1}$, so
$\lim_{m\to\infty}{\delta_{m}}=\infty$.

By construction, $0<\varepsilon_{m}\gamma_{m}\leq\varepsilon_{m}\delta_{m}$
for all $m\in\mathbb{N}$, so the convergence of
$\tsum\slimits@_{m=0}{\varepsilon_{m}\delta_{m}}$ to the recursive real
$2\varepsilon$ implies that $\tsum\slimits@_{m=0}{\varepsilon_{m}\gamma_{m}}$
also converges to a recursive real by Proposition II.3.8. Finally,
$\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$ is nondecreasing by construction.
∎

###### Proof of Theorem V.3.12..

First, $\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}$ converging to a
recursive real implies that
$\tsum\slimits@_{m=0}{\frac{f(2^{m+1})}{2^{m}}}=2\left(\tsum\slimits@_{m=0}{\frac{f(2^{m+1})}{2^{m+1}}}-f(1)\right)$
converges to a recursive real. Then
$\tsum\slimits@_{m=0}{\frac{f(2^{m+1})+1}{2^{m}}}=\tsum\slimits@_{m=0}{\frac{f(2^{m+1})}{2^{m}}}+2$
converges to a recursive real, so Proposition II.3.8 implies that
$\tsum\slimits@_{m=0}{\frac{\lceil f(2^{m+1})\rceil}{2^{m}}}$ converges to a
recursive real.

Applying Lemma V.3.13 to $\langle\lceil f(2\cdot
2^{m})\rceil/2^{m}\rangle_{m\in\mathbb{N}}$ yields a nondecreasing, recursive
sequence $\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$ of positive integers
tending towards infinity such that $\tsum\slimits@_{m=0}{\frac{\lceil
f(2^{m+1})\rceil}{2^{m}}\gamma_{m}}$ converges. Note that the proof of Lemma
V.3.13 shows that we may assume without loss of generality that
$\gamma_{m}\leq m+1$ for all $m\in\mathbb{N}$.

Define $\varepsilon_{m}=\frac{\lceil
f(2^{m+1})\rceil}{2^{m}}\gamma_{m}+\frac{2m^{2}}{2^{m}}\gamma_{m}$. By the
definition of $\langle\gamma_{m}\rangle_{m\in\mathbb{N}}$,
$\tsum\slimits@_{m=0}{\frac{\lceil f(2^{m+1})\rceil}{2^{m}}\gamma_{m}}$
converges. Because $\gamma_{m}\leq m+1$,
$\tsum\slimits@_{m=0}{\frac{2m^{2}}{2^{m}}\gamma_{m}}$ also converges. Thus,
$\tsum\slimits@_{m=0}{\varepsilon_{m}}$ converges. Additionally, both $\langle
2^{m}\varepsilon_{m}\rangle_{m\in\mathbb{N}}$ and $\langle
2^{m}\varepsilon_{m}\gamma_{m}^{-1}\rangle_{m\in\mathbb{N}}$ are strictly
increasing, recursive sequences of natural numbers.

Define $g\colon\mathbb{N}\to{[0,\infty)}$ by setting

$g(n)\mathrel{{\vdotdot}{\equal}}\frac{2^{m+1}\varepsilon_{m+1}\gamma_{m+1}^{-1}-2^{m}\varepsilon_{m}\gamma_{m}^{-1}}{2^{m+1}\varepsilon_{m+1}-2^{m}\varepsilon_{m}}(n-2^{m}\varepsilon_{m})+2^{m}\varepsilon_{m}\gamma_{m}^{-1}$

for $2^{m}\varepsilon_{m}\leq n<2^{m+1}\varepsilon_{m+1}$. For $0\leq
n<\varepsilon_{0}$, let $g(n)\mathrel{{\vdotdot}{\equal}}\gamma_{0}^{-1}n$. In
other words, we set $g(0)\mathrel{{\vdotdot}{\equal}}0$ and
$g(2^{m}\varepsilon_{m})\mathrel{{\vdotdot}{\equal}}2^{m}\varepsilon_{m}\gamma_{m}^{-1}$
for $m\in\mathbb{N}$, then take $g$ to be defined linearly between consecutive
points in the sequence $\langle
0,0\rangle,\langle\varepsilon_{0},\varepsilon_{0}\gamma_{0}^{-1}\rangle,\langle
2\varepsilon_{1},2\varepsilon_{2}\gamma_{1}^{-1}\rangle,\ldots$. We make the
following observations:

  * •

By the definition of $g$ above, $g$ is recursive.

  * •

Because the sequences $\langle 2^{m}\varepsilon_{m}\rangle_{m\in\mathbb{N}}$
and $\langle 2^{m}\varepsilon_{m}\gamma_{m}^{-1}\rangle_{m\in\mathbb{N}}$ are
both strictly increasing, $g$ is nondecreasing.

  * •

To show that $\lim_{n\to\infty}{\frac{g(n)}{n}}=0$, the piecewise linearity of
$g$ means that it suffices to show that
$\lim_{m\to\infty}{\frac{g(2^{m}\varepsilon_{m})}{2^{m}\varepsilon_{m}}}=0$.
Indeed,

$\lim_{m\to\infty}{\frac{g(2^{m}\varepsilon_{m})}{2^{m}\varepsilon_{m}}}=\lim_{m\to\infty}{\frac{2^{m}\varepsilon_{m}\gamma_{m}^{-1}}{2^{m}\varepsilon_{m}}}=\lim_{m\to\infty}{\gamma_{m}^{-1}}=0.$

  * •

$g(2^{m}\varepsilon_{m})\geq f(2^{m+1})+2m$:

$\displaystyle g(2^{m}\varepsilon_{m})$
$\displaystyle=2^{m}\varepsilon_{m}\gamma_{m}^{-1}$ $\displaystyle=\lceil
f(2^{m+1})\rceil\gamma_{m}\gamma_{m}^{-1}+2m^{2}\gamma_{m}\gamma_{m}^{-1}$
$\displaystyle\geq\lceil f(2^{m+1})\rceil+2m$ $\displaystyle\geq
f(2^{m+1})+2m.$

Thus, $g$ is an order function and

$\liminf_{m}{\frac{g(2^{m}\varepsilon_{m})-f(2\cdot 2^{m})}{m}}\geq 2>1.$

Theorem V.3.7 then implies
$\mathrm{COMPLEX}(g)\mathrel{{}_{\mathrm{s}}}\mathrm{SC}(f)$.

∎

####  V.3.3 Strong Shift Complexity and Depth

Although there exist order functions $f$ for which $\mathrm{SC}(f)$ is
negligible, the situation for generalized strong shift complexity is more
favorable with respect to depth, completely answering Question V.3.2.

######  Theorem V.3.14.

[23, Theorem 5, essentially] $\mathrm{SSC}(f,c)$ is a deep $\Pi^{0}_{1}$ class
for any order function $f$ satisfying $\limsup_{n}{\frac{f(n)}{n}}<1$ and any
$c\in\mathbb{N}$.

###### Proof.

With $\mathbf{M}$ a universal left r.e. continuous semimeasure on $\\{0,1\\}$,
by Proposition II.4.3 there is a partial recursive functional $\Psi$ such that
for every $\sigma\in\\{0,1\\}$,

$\mathbf{M}(\sigma)=\lambda(\Psi^{-1}(\sigma))=\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\Psi^{X}\supseteq\sigma\\}).$

For a fixed $n\in\mathbb{N}$, say $Y\in\\{0,1\\}\cup\\{0,1\\}^{\mathbb{N}}$
_avoids_ a $\vec{\tau}=\langle\tau_{0},\tau_{1},\ldots,\tau_{N-1}\rangle$ if
$|Y|\geq N+n-1$ and $Y({[k,k+n)})\neq\tau_{k}$ for all
$k\in\\{0,1,2,\ldots,N-1\\}$.

Our approach, roughly, involves us finding, for a fixed length $n$, a sequence
$\vec{\tau}$ of ‘forbidden’ strings $\tau_{0},\tau_{1},\ldots,\tau_{N-1}$
(where $N=N(n,m)$) of length $n$ such that

$\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$\Psi(X)$ avoids
$\vec{\tau}$}\\})<2^{-m}.$

By showing that such a $\vec{\tau}$ can be chosen so that
$\operatorname{KP}(\tau_{k}\mid k,n)$ is bounded for all $k,n$, it will follow
that it is exceeded by $f(n)-c$ for all sufficiently large $n$. Hence, if an
output $Y$ of $\Psi$ is strongly $f$-shift complex, then it avoids
$\vec{\tau}$, and $\lambda(\Psi^{-1}[\mathrm{SSC}(f,c)])<2^{-m}$.

As in the proof of Theorem V.1.3, an arbitrary output of $\Psi$ need not be in
$\\{0,1\\}^{\mathbb{N}}$. However, also like in Theorem V.1.3, we only need
$|\Psi^{X}|\geq N+n-1$ for the notion of avoiding
$\vec{\sigma}\in(\\{0,1\\}^{n})^{N}$ to be well-defined. As such, define

$S\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid|\Psi^{X}|\geq
N+n-1\\}$

where $N=N(n,m)$ is the smallest natural number for which

$\left(1-\frac{1}{2^{n}}\right)^{N}<2^{-(m+1)}.$

$S$ is $\Sigma^{0}_{1}$, so there exists a recursive sequence
$\langle\sigma_{n}\rangle_{n\in\mathbb{N}}$ of pairwise incompatible strings
such that
$S=\tbigcup\slimits@_{n\in\mathbb{N}}{\left\llbracket\sigma_{n}\right\rrbracket}$.
Let $\alpha=\lambda(S)$, so that $\langle\lambda\left(\tbigcup\slimits@_{k\leq
n}{\left\llbracket\rho_{k}\right\rrbracket}\right)\rangle_{n\in\mathbb{N}}$
converges monotonically to $\alpha$ from below. Let $i_{0}$ be the largest
natural number $i$ such that $\alpha_{i}\mathrel{{\vdotdot}{\equal}}i\cdot
2^{-m}/3<\alpha$, so that $\alpha-\alpha_{i_{0}}<2^{-(m+1)}$. Then let $p$ be
the smallest natural number such that $\lambda\left(\tbigcup\slimits@_{k\leq
p}{\left\llbracket\sigma_{k}\right\rrbracket}\right)\geq\alpha_{i_{0}}$ and
finally define

$\tilde{S}\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@_{k\leq
p}{\left\llbracket\sigma_{k}\right\rrbracket}.$

$\tilde{S}$ is a recursive subset of $S$ and
$\lambda(S\setminus\tilde{S})<2^{-(m+1)}$. By virtue of being a subset of $S$,
$|\Psi^{X}|\geq N+n-1$ for all $X\in S$. Define $\mu$ on $\\{0,1\\}^{N+n-1}$
by

$\mu(\tau)\mathrel{{\vdotdot}{\equal}}\lambda(\tilde{S})^{-1}\cdot\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X\in\tilde{S}$
and $\Psi^{X}\supseteq\tau$}\\}).$

$\mu$ is a probability measure on $\\{0,1\\}^{N+n-1}$, and the recursiveness
of $\tilde{S}$ implies $\mu$ is computable.

For a fixed $Y\in\\{0,1\\}^{\geq N+n-1}$, the probability that
$\vec{\tau}\in(\\{0,1\\}^{n})^{N}$ is avoided by $Y$ (taken with respect to
the uniform probability measure $\nu$ on $(\\{0,1\\}^{n})^{N}$, or
equivalently the $N$-fold product of the uniform probability measures on
$\\{0,1\\}^{n}$) is equal to

$\left(1-\frac{1}{2^{n}}\right)^{N}<\frac{\varepsilon}{2}.$

Write

$E\mathrel{{\vdotdot}{\equal}}\\{\langle
X,\vec{\tau}\rangle\in\\{0,1\\}^{\mathbb{N}}\times(\\{0,1\\}^{n})^{N}\mid\text{$X\in\tilde{S}$
and $\Phi^{X}$ avoids $\vec{\tau}$}\\}.$

By Fubini’s Theorem,

$\displaystyle\int{\left(\int{\chi_{E}(X,\vec{\tau})\,\mathrm{d}\lambda}\right)\,\mathrm{d}\nu}$
$\displaystyle=(\lambda\times\nu)(E)$
$\displaystyle=\int{\left(\int{\chi_{E}(X,\vec{\sigma})\,\mathrm{d}\nu}\right)\,\mathrm{d}\lambda}$
$\displaystyle=\int{(1-2^{-n})^{N}\,\mathrm{d}\lambda}$
$\displaystyle=(1-2^{-n})^{N}$ $\displaystyle<2^{-(m+1)}.$

If $\int{\chi_{E}(X,\vec{\tau})\,\mathrm{d}\lambda}\geq 2^{-(m+1)}$ for every
$\vec{\tau}\in(\\{0,1\\}^{n})^{N}$, we reach a contradiction. Thus, there is a
least one sequence $\vec{\tau}\in(\\{0,1\\}^{n})^{N}$ with the desired
property, i.e., for which

$\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X\in\tilde{S}$ and $\Psi^{X}$
avoids $\vec{\tau}$}\\})<2^{-(m+1)},$

and hence

$\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X\in S$ and $\Psi^{X}$ avoids
$\vec{\tau}$}\\})<2^{-(m+1)}+2^{-(m+1)}=2^{-m}.$

Let $c_{1}\in\mathbb{N}$ be such that $\operatorname{KP}(\sigma)\leq
2\log_{2}|\sigma|+c_{1}$ for all $\sigma\in\\{0,1\\}$. An index for
$\tilde{S}$ can be found effectively as a function of $n$, $m$, and $i_{0}$,
and such an index can be used to compute a
$\vec{\tau}=\langle\tau_{0},\tau_{1},\ldots,\tau_{N-1}\rangle$ for which
$\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X\in\tilde{S}$ and $\Psi^{X}$
avoids $\vec{\tau}$}\\})<2^{-(m+1)}$. As such, there is a constant
$c_{2}\in\mathbb{N}$ (independent of $k$, $n$, $m$, and $i_{0}$) such that
$\operatorname{KP}(\tau_{k}\mid k,n,i_{0})\leq\operatorname{KP}(m)+c_{2}$ for
all $k$, $n$, and $i_{0}$. Although $i_{0}$ cannot in general be found
recursively as a function of $\langle n,m\rangle$, we have the bound
$i_{0}\leq(2^{-m}/3)^{-1}=3\cdot 2^{m}$. Thus,

$\operatorname{KP}(i_{0})\max_{0\leq i\leq 3\cdot
2^{m}}{\operatorname{KP}(i)}\leq\max_{0\leq i\leq 3\cdot
2^{m}}{(2\log_{2}i+c_{1})}\leq 2m+2\log_{2}3+c_{1}.$

Finally, there is $c_{3}\in\mathbb{N}$ such that for all
$\sigma,\rho_{1},\rho_{2},\rho_{3}\in\\{0,1\\}$ we have
$\operatorname{KP}(\sigma\mid\rho_{1},\rho_{2})\leq\operatorname{KP}(\sigma\mid\rho_{1},\rho_{2},\rho_{3})+\operatorname{KP}(\rho_{3})+c_{3}$.
Thus,

$\displaystyle\operatorname{KP}(\tau_{k}\mid k,n)$
$\displaystyle\leq\operatorname{KP}(\tau_{k}\mid
k,n,i_{0})+\operatorname{KP}(i_{0})+c_{3}$
$\displaystyle\leq(\operatorname{KP}(m)+c_{2})+2m+2\log_{2}3+c_{1}+c_{3}$
$\displaystyle\leq(2\log_{2}m+c_{1}+c_{2})+2m+2\log_{2}3+c_{1}+c_{3}$
$\displaystyle=2m+2\log_{2}m+(2\log_{2}3+2c_{1}+c_{2}+c_{3}).$

Let $d=2\log_{2}3+2c_{1}+c_{2}+c_{3}$ and let $n=n(m)$ be the least such that

$f(n)-c>2m+2\log_{2}m+d.$

Suppose $\Psi(X)$ is strongly $(f,c)$-shift complex, so that
$\Psi^{X}=\Psi(X)\in\\{0,1\\}^{\mathbb{N}}$ (therefore $X\in S$) and
$\operatorname{KP}(\Psi(X)({[k,k+n)})\mid k,n)\geq f(n)-c$ for all $n,k$. For
a sufficiently large $n$,

$\operatorname{KP}(\Psi(X)([k,k+n))\mid k,n)\geq
f(n)-c>\operatorname{KP}(\sigma_{k}\mid k,n)$

so $\Psi(X)([k,k+n))\neq\sigma_{k}$, hence $\Psi(X)$ avoids $\vec{\sigma}$.
Define $r\colon\mathbb{N}\to\mathbb{N}$ by
$r(m)\mathrel{{\vdotdot}{\equal}}N(n(m),m)+n(m)-1$, which is a recursive
function. Then

$\displaystyle\mathbf{M}(\mathrm{SSC}(f,c){\upharpoonright}\,r(m))$
$\displaystyle\leq\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$|\Psi^{X}|\geq
r(m)$ and $\Psi^{X}{\upharpoonright}\,r(m)$ is strongly $(f,c)$-shift
complex}\\})$
$\displaystyle\leq\lambda(\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X\in S$ and
$\Psi^{X}$ avoids $\vec{\tau}$}\\})$ $\displaystyle<2^{-m}.$

Hence, $\mathrm{SSC}(f,c)$ is deep. ∎

###  V.4 Open Questions

There are a great many open questions concerning shift complexity and
generalized shift complexity. Just focusing on the classes
$\mathrm{SC}(\delta)$ and $\mathrm{SSC}(\delta)$, basic questions about their
weak degrees remain open, such as separating $\mathrm{SC}(\alpha)$ and
$\mathrm{SC}(\beta)$ when $\alpha\neq\beta$:

######  Question V.4.1.

Are there rational numbers $0<\alpha<\beta<1$ such that
$\mathrm{SC}(\alpha)\mathrel{{}_{\mathrm{w}}}\mathrm{SC}(\beta)$?
$\mathrm{SC}(\alpha)\mathrel{<_{\mathrm{w}}}\mathrm{SC}(\beta)$?

######  Question V.4.2.

Are there rational numbers $0<\alpha<\beta<1$ such that
$\mathrm{SSC}(\alpha)\mathrel{{}_{\mathrm{w}}}\mathrm{SSC}(\beta)$?
$\mathrm{SSC}(\alpha)\mathrel{<_{\mathrm{w}}}\mathrm{SSC}(\beta)$?

The relationship between the classes $\mathrm{SC}(\alpha)$ and
$\mathrm{SSC}(\beta)$ is especially unclear. We know that
$\mathrm{SC}(\alpha)\mathrel{{}_{\mathrm{s}}}\mathrm{SSC}(\alpha)$, but not
much more than that is known.

######  Question V.4.3.

Is there a rational $\delta\in(0,1)$ such that
$\mathrm{SC}(\delta)\mathrel{{}_{\mathrm{w}}}\mathrm{SSC}(\delta)$?

If Question V.4.3 is answered in the negative (so
$\mathrm{SC}(\delta)\mathrel{<_{\mathrm{w}}}\mathrm{SSC}(\delta)$ for all
$\delta\in(0,1)$), we might turn to comparing $\mathrm{SSC}(\alpha)$ and
$\mathrm{SC}(\beta)$ for some $0<\alpha<\beta<1$.

######  Question V.4.4.

Given a rational $0<\beta<1$, does
$\mathrm{SSC}(\alpha)\mathrel{{}_{\mathrm{w}}}\mathrm{SC}(\beta)$ hold for all
rationals $0<\alpha<\beta$? If not, for _some_ $\alpha<\beta$?

Although $\mathrm{SC}(\delta,c)$ is deep for every rational $\delta\in(0,1)$
and $c\in\mathbb{N}$, it is unclear if $\mathrm{SC}(\delta)$ is of deep degree
– while
$\mathrm{COMPLEX}(\alpha,c)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(\beta)$
for any $0<\alpha<\beta$ such that $\mathrm{COMPLEX}(\alpha,c)\neq\emptyset$,
it is unclear if this holds when complexity is replaced with shift complexity.

######  Question V.4.5.

Are $\mathrm{SC}(\delta)$ or $\mathrm{SSC}(\delta)$ of deep degree in
$\mathcal{E}_{\mathrm{w}}$ for every rational $\delta\in(0,1)$?

More generally, we may ask similar questions with generalized shift
complexity:

######  Question V.4.6.

Given order functions $f\colon\mathbb{N}\to{[0,\infty)}$ and
$g\colon\mathbb{N}\to{[0,\infty)}$, when do we have
$\mathrm{SC}(f)\mathrel{<_{\mathrm{w}}}\mathrm{SC}(g)$?

Partial answers to Question V.4.6 exist. For example, Corollary V.3.10 allows
us to separate the weak degrees
$\mathop{\deg_{\mathrm{w}}}(\mathrm{SC}(\lambda n.n^{\alpha}))$:

######  Proposition V.4.7.

If $0<\alpha<\beta<1$ are rational numbers, then $\mathrm{SC}(\lambda
n.n^{\alpha})\mathrel{<_{\mathrm{w}}}\mathrm{SC}(\lambda n.n^{\beta})$.

###### Proof.

Corollary V.3.10 shows

$\mathrm{SC}(\lambda
n.n^{\alpha})\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(\lambda
n.n^{(\alpha+\beta)/2})\mathrel{<_{\mathrm{w}}}\mathrm{COMPLEX}(\lambda
n.n^{\beta})\mathrel{{}_{\mathrm{w}}}\mathrm{SC}(\lambda n.n^{\beta}).$

∎

A variant of Question V.4.6 can be phrased as an existence question:

######  Question V.4.8.

Given an order function $f\colon\mathbb{N}\to{[0,\infty)}$ for which
$\limsup_{n}{\frac{f(n)}{n}}<1$, for which order functions
$g\colon\mathbb{N}\to{[0,\infty)}$ can we guarantee that
$\mathrm{SC}(f)\setminus\mathrm{SC}(g)\neq\emptyset$?

The depth and/or negligibility of $\mathrm{SC}(f,c)$ for $f$ satisfying
$\limsup_{n}{\frac{f(n)}{n}}=0$ is only partially addressed by Theorem V.3.12.

######  Question V.4.9.

Does there exist an order function $f\colon\mathbb{N}\to{[0,\infty)}$ such
that $\limsup_{n}{\frac{f(n)}{n}}=0$ but $\mathrm{SC}(f,c)$ is deep for all
$c\in\mathbb{N}$? Negligible?

A particular instance of Question V.4.9 asked by Rumyantsev is for $f$ defined
by $f(n)\mathrel{{\vdotdot}{\equal}}n/\log_{2}n$, where
$\tsum\slimits@_{m=0}{\frac{f(2^{m})}{2^{m}}}=\tsum\slimits@_{m=0}{\frac{2^{m}/m}{2^{m}}}=\tsum\slimits@_{m=0}{\frac{1}{m}}=\infty$
and hence not addressed by Theorem V.3.12.

There are still open questions about the relationship between (generalized)
shift complexity and (generalized) strong shift complexity with the slow-
growing $\mathrm{LU\kern-0.50003ptA}$ hierarchy.

######  Question V.4.10.

Does there exist any rational $\delta\in(0,1)$ and $c\in\mathbb{N}$ such that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{SC}(\delta,c)$?

Likewise, there are still many open questions about the relationship between
generalized shift complexity and complexity.

######  Question V.4.11.

For what order functions $f\colon\mathbb{N}\to{[0,\infty)}$ is there a sub-
identical order function $g\colon\mathbb{N}\to{[0,\infty)}$ such that
$\mathrm{SC}(f)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(g)$?

##  Chapter VI Avoidance – Slow-Growing versus Fast-Growing

A result of Khan & Miller using bushy tree forcing shows that the classes
$\mathrm{DNR}(p)$ do not cleanly stack one atop the other as $p$ ranges
through the order functions:

######  Theorem.

[16, Theorem 3.11] Given any order function $p\colon\mathbb{N}\to(1,\infty)$,
there is an order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{DNR}(p)$ and $\mathrm{DNR}(q)$ are weakly incomparable.

Our aim in this chapter is to lift this result to the
$\mathrm{LU\kern-0.50003ptA}$ hierarchy with further generality and adding the
guarantee that $q$ can be chosen to be slow-growing:

######  Theorem VI.2.1.

For all order functions $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$, there exists a slow-growing order
function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(q)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(p_{2})$.
In particular, for any order function $p\colon\mathbb{N}\to(1,\infty)$, there
exists a slow-growing order function $q\colon\mathbb{N}\to(1,\infty)$ such
that $\mathrm{LU\kern-0.50003ptA}(p)$ and $\mathrm{LU\kern-0.50003ptA}(q)$ are
weakly incomparable.

In Section VI.1 we cover the necessary combinatorial tools, those of $k$-bushy
trees and the associated notions of being $k$-big or $k$-small above a string.

In Section VI.2, we prove the following variant of Theorem VI.2.1 where
avoidance is taken with respect to individual partial recursive functions.

######  Theorem VI.2.2.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and $p_{2}\colon(1,\infty)$ are
order functions, $u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing
order function, $\psi_{1}$ and $\psi_{2}$ are universal partial recursive
functions, and $\psi_{3}$ and $\psi_{4}$ are partial recursive functions. Then
there exists a order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$q\circ u$ is slow-growing and

$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2}).$

In Section VI.3, we deduce from Theorem VI.2.2 a generalization in which
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})$ and
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ are replaced with
$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{1}}(p_{1})$ and
$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{2}}(q\circ u)$, respectively,
where $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ may be are families of universal
partial recursive functions satisfying a condition we term “translationally
bounded from above”, of which the family of linearly universal partial
recursive functions is included.

######  Theorem VI.3.7.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function,
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are nonempty families of universal
partial recursive functions which are each translationally bounded from above,
and $\psi_{1}$ and $\psi_{2}$ are partial recursive functions. Then there
exists an order function $q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ u$
is slow-growing and for which

$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2}).$

Theorem VI.2.1 is then an easy consequence of Theorem VI.3.7.

In Section VI.4, we use Theorem VI.2.1 to deduce the following implications
concerning $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$.

######  Theorem VI.4.1.

$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ is not of deep degree.

######  Theorem VI.4.2.

There is no order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.

######  Theorem VI.4.3.

$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$.

In Section VI.5, we prove the following variant of Theorem VI.2.2 where $q$
being slow-growing is strengthened to
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ being of deep degree.

######  Theorem VI.5.1.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function,
$\psi_{1}$ and $\psi_{2}$ are universal partial recursive functions, and
$\psi_{3}$ and $\psi_{4}$ are partial recursive functions. Then there exists a
order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ is of deep degree and

$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2}).$

###  VI.1 Bushy Trees

The main tool we use in the proof of Theorem VI.2.1 and Theorem VI.2.2 is
bushy tree forcing, which was developed by Kumabe in 1993 to answer
affirmatively a question of Sacks which asked if there were $\mathrm{DNR}$
reals of minimal Turing degree. The proof was never published, but a draft was
in private circulation in 1996. The technique in its current form was
introduced in a 2009 publication by Kumabe and Lewis to give a simplified
version of Kumabe’s original proof.

Bushy tree forcing has since become a standard tool when working with
$\mathrm{DNR}$ and has been described [1] as, “the canonical forcing notion
used in the study of $\mathrm{DNR}$ functions.”

######  Definition VI.1.1 ($n$-bushy above $\sigma$).

Suppose $\sigma\in\mathbb{N}$. A tree $T\subseteq\mathbb{N}$ is _$n$ -bushy
above $\sigma$_ if every element of $T$ is compatible with $\sigma$ and every
$\tau\in T$ which extends $\sigma$ is either a leaf or else has at least $n$
immediate extensions in $T$. $\sigma$ is known as the _stem_ of $T$.

Subsets $A$ of $\mathbb{N}$ for which we have many ways of extending $\sigma$
to an element of $A$ are ‘big’. Otherwise, they are ‘small’.

######  Definition VI.1.2 ($n$-big, $n$-small above $\sigma$).

Suppose $\sigma\in\mathbb{N}$. A set $B\subseteq\mathbb{N}$ is _$n$ -big above
$\sigma$_ if there is a finite tree $T$ which is $n$-bushy tree above $\sigma$
and for which its leaves lie in $B$.

If $B$ is not $n$-big above $\sigma$, then $B$ is said to be _$n$ -small above
$\sigma$_.

Our arguments are based on the idea that there are ‘bad’ sets of strings which
we wish to avoid. If we can ensure that those ‘bad’ sets of strings are
sufficiently small, then we can construct a real $X\in\mathbb{N}^{\mathbb{N}}$
none of whose initial segments lie in those ‘bad’ sets.

In [16] several fundamental combinatorial lemmas are identified which are
reproduced below, sometimes with minor modifications suited to our needs.

######  Lemma VI.1.3 (Concatenation Property).

[16, Lemma 2.6] Suppose $A\subseteq\mathbb{N}$ is $n$-big above $\sigma$ and
$\langle A_{\tau}\rangle_{\tau\in A}$ is a family of subsets of $\mathbb{N}$
indexed by $A$. If $A_{\tau}$ is $n$-big above $\tau$ for every $\tau\in A$,
then $\tbigcup\slimits@_{\tau\in T}{A_{\tau}}$ is $n$-big above $\sigma$.

###### Proof.

For each $\tau\in A$, let $T_{\tau}$ be a finite $n$-bushy tree above $\tau$
all of whose leaves lie in $A_{\tau}$. Let $T$ be a finite $n$-bushy tree
above $\sigma$ all of whose leaves lie in $A$. Define $\hat{T}$ to be the tree
obtained by taking the union of $T$ with the trees $T_{\tau}$ where $\tau$ is
a leaf of $T$ in $A$. We claim that $\hat{T}$ is $n$-bushy above $\sigma$.
Because every string in $\hat{T}$ extends an element of $T$, it follows that
every string in $\hat{T}$ extends $\sigma$. Now suppose $\rho$ is a string in
$\hat{T}$ extending $\sigma$ and which is not a leaf. We consider three cases:

Case 1:

If $\rho$ is a member of $T$ and not a leaf of $T$, then the fact that $T$ is
$n$-bushy above $\sigma$ implies it has at least $n$ immediate extensions in
$T\subseteq\hat{T}$.

Case 2:

If $\rho$ is a leaf of $T$, then $\rho=\tau$ for some $\tau\in A$; $\tau$
extends itself (improperly), so $T_{\tau}$ being $n$-bushy above $\tau$
implies it is either a leaf of $T_{\tau}$ (and hence of $\hat{T}$) or it has
at least $n$ immediate extensions in $T_{\tau}\subseteq\hat{T}$.

Case 3:

If $\rho$ is not a member of $T$, then $\rho\in T_{\tau}$ for some $\tau\in
A$. The argument then follows exactly as in Case 2.

It only remains to show that the leaves of $\hat{T}$ lie in
$\tbigcup\slimits@_{\tau\in A}{A_{\tau}}$. Indeed, the leaves of $\hat{T}$ are
exactly the leaves of $A_{\tau}$ for all $\tau\in A$, which each lie in
$A_{\tau}$, respectively, and hence in $\tbigcup\slimits@_{\tau\in
A}{A_{\tau}}$. ∎

######  Lemma VI.1.4 (Smallness Preservation Property).

[16, Lemma 2.7] Suppose that $B,C\subseteq\mathbb{N}$, $m,n\in\mathbb{N}$, and
$\sigma\in\mathbb{N}$. If $B$ is $m$-small above $\sigma$ and $C$ is $n$-small
above $\sigma$, then $B\cup C$ is $(n+m-1)$-small above $\sigma$.

###### Proof.

Suppose for the sake of a contradiction that $B\cup C$ is not $(n+m-1)$-small
above $\sigma$, i.e., $(n+m-1)$-big above $\sigma$. Then there exists a finite
tree $T$ which is $(n+m-1)$-bushy above $\sigma$ all of whose leaves lie in
$B\cup C$. We will label each element of $T$ by either a ‘B’ or a ‘C’,
starting with leaves and working our way towards the stem $\sigma$. Label a
leaf of $T$ ‘B’ if it lies in $B$ and ‘C’ otherwise. If an extension $\tau$ of
$\sigma$ in $T$ has not been labeled but all of its proper extensions have
been, then label $\tau$ ‘B’ if at least $m$ of its immediate successors have
‘B’ label, and ‘C’ otherwise (by the pigeonhole principle, there must be at
least $n$ immediate successors labeled ‘C’). Continue in this way until
$\sigma$ itself has been labeled.

If $\sigma$ has been labeled ‘B’, then the set $T_{\mathrm{B}}$ of all
extensions of $\sigma$ (along with the initial segments of $\sigma$) labeled
‘B’ is a finite tree which is $m$-bushy above $\sigma$. Otherwise, the set
$T_{\mathrm{C}}$ of all extensions of $\sigma$ (along with the initial
segments of $\sigma$) labeled ‘C’ is $n$-bushy above $\sigma$. In either case,
we reach a contradiction. ∎

######  Lemma VI.1.5 (Small Set Closure Property).

[16, Lemma 2.8, essentially] Suppose $B\subseteq\mathbb{N}$ is $k$-small above
$\sigma$. Let $C=\\{\tau\in\mathbb{N}\mid\text{$B$ is $k$-big above
$\tau$}\\}$. Then $C$ is $k$-small above $\sigma$ and is _$k$ -closed_, i.e.,
if $C$ is $k$-big above a string $\rho$, then $\rho\in C$.

Moreover, the upward closure of $C$ is $k$-small above $\sigma$ and
$k$-closed.

###### Proof.

Suppose for the sake of a contradiction that $C$ is $k$-big above $\sigma$.
Then, by Lemma VI.1.3, $B$ is $k$-big above $\sigma$, yielding a
contradiction.

The same reasoning can be applied to show that if $C$ is $k$-big above a
string $\rho$, then $B$ is $k$-big above $\rho$ and hence $\rho\in C$.

Now consider the upward closure
$C^{\uparrow}\mathrel{{\vdotdot}{\equal}}\\{\rho\in\\{0,1\\}\mid\exists\tau\in
C\,(\tau\subseteq\rho)\\}$ of $C$. The following lemma shows that
$C^{\uparrow}$ is similarly $k$-small above $\sigma$ and $k$-closed.

######  Lemma VI.1.6.

Suppose $B\subseteq\mathbb{N}$ and $\sigma\in\mathbb{N}$. Then $B$ is $k$-big
above $\sigma$ if and only if its upward closure $B^{\uparrow}$ is $k$-big
above $\sigma$.

###### Proof.

If $B$ is $k$-big above $\sigma$, then any finite $k$-bushy tree $T$ above
$\sigma$ realizing this also shows that $B^{\uparrow}$ is $k$-big above
$\sigma$.

Conversely, suppose $B^{\uparrow}$ is $k$-big above $\sigma$, and let $T$ be a
finite $k$-bushy tree above $\sigma$ whose leaves are within $B^{\uparrow}$.
Let

$\tilde{T}=\\{\tau\in T\mid\tau\in
B^{\uparrow}\wedge\tau{\upharpoonright}\,(|\tau|-1)\notin B^{\uparrow}\\}.$

$\tilde{T}$ is a tree, as if $\tau\in T$ and
$\sigma\mathrel{\ooalign{\hss\raise 1.29167pt\hbox{$\subset$}\hss\cr\kern
0.86108pt\raise-2.15277pt\hbox{\scalebox{0.7}{$\mathrel{\ooalign{\hss\hbox{\scalebox{1.4}{$-$}}\hss\cr\kern
0.86108pt\raise-0.43057pt\hbox{\rotatebox{45.0}{$-$}}}}$}}}}\tau$, then
$\sigma$ is an element of $T\setminus B^{\uparrow}$, and $B^{\uparrow}$ being
upward closed implies no initial segment of $\sigma$ is in $B^{\uparrow}$, so
$\sigma\in\tilde{T}$. ∎

∎

######  Definition VI.1.7 ($k$-Closure).

If $B\subseteq\mathbb{N}$ is $k$-small above $\sigma$, then its _$k$ -closure_
is the upward closure of the set $\\{\tau\in\mathbb{N}\mid\text{$B$ is $k$-big
above $\tau$}\\}$.

In addition to the above lemmas, we also collect a series of facts which
either follow quickly from those above lemmas or else follow immediately from
the definitions.

######  Lemma VI.1.8.

Suppose $\sigma\in\mathbb{N}$ and $B,C\subseteq\mathbb{N}$ are given.

  1. (a)

If $B$ is $\ell$-big above $\sigma$ and $k<\ell$, then $B$ is $k$-small above
$\sigma$.

  2. (b)

If $B$ is $k$-small above $\sigma$ and $k<\ell$, then $B$ is $\ell$-small
above $\sigma$.

  3. (c)

If $B=B_{1}\cup B_{2}\cup\@cdots\cup B_{n}$ is $n\cdot k$-big above $\sigma$
and $n,k>0$, then there exists $i\in\\{1,2,\ldots,n\\}$ such that $B_{i}$ is
$k$-big above $\sigma$.

  4. (d)

If $B\subseteq C$ and $B$ is $k$-big above $\sigma$, then $C$ is $k$-big above
$\sigma$.

  5. (e)

If $B\subseteq C$ and $C$ is $k$-small above $\sigma$, then $B$ is $k$-small
above $\sigma$.

  6. (f)

If $B$ is $k$-small above $\sigma$ and $k$-closed and $C$ is $k$-big above
$\sigma$, then there exists a $\tau\in C\setminus B$ which extends $\sigma$.

###### Proof.

  1. (a)

If $T$ is a finite tree which is $\ell$-bushy above $\sigma$ and all of whose
leaves lie in $B$, then $T$ is $k$-bushy above $\sigma$. Thus, $B$ is $k$-big
above $\sigma$.

  2. (b)

If $B$ is $\ell$-big above $\sigma$, then (a) above shows that $B$ is $k$-big
above $\sigma$, a contradiction.

  3. (c)

Suppose for the sake of a contradiction that $B_{i}$ is $k$-small above
$\sigma$ for every $i\in\\{1,2,\ldots,n\\}$. By repeated applications of Lemma
VI.1.4 we find that $B$ is $n\cdot k-(n-1)=(n\cdot(k-1)+1)$-small above
$\sigma$. $n\cdot(k-1)+1<n\cdot k$, so (a) above gives a contradiction.

  4. (d)

A finite $k$-bushy tree above $\sigma$ whose leaves are in $B$ is a finite
$k$-bushy tree above $\sigma$ whose leaves are in $C\supseteq B$.

  5. (e)

If $B$ is $k$-big above $\sigma$, then (d) above implies $C$ is $k$-big above
$\sigma$, a contradiction.

  6. (f)

Suppose for the sake of a contradiction that there is no $\tau\in C\setminus
B$ extending $\sigma$. Because $C$ is $k$-big above $\sigma$, there exists a
$k$-bushy tree $T$ above $\sigma$ all of whose leaves lie in $C$. But every
leaf of $T$ is an extension of $\sigma$ in $C$, which by hypothesis implies it
lies in $B$, so $T$ is a $k$-bushy tree above $\sigma$ all of whose leaves lie
in $B$, contradicting the hypothesis that $B$ is $k$-small above $\sigma$.

∎

###  VI.2 Avoidance of Individual Universal Partial Recursive Functions

We wish to use what Khan & Miller term ‘basic’ bushy tree forcing [16] – in
which we approximate our generic real with finite strings – to prove the
following result.

######  Theorem VI.2.1.

For all order functions $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$, there exists a slow-growing order
function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(q)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(p_{2})$.
In particular, for any order function $p\colon\mathbb{N}\to(1,\infty)$, there
exists a slow-growing order function $q\colon\mathbb{N}\to(1,\infty)$ such
that $\mathrm{LU\kern-0.50003ptA}(p)$ and $\mathrm{LU\kern-0.50003ptA}(q)$ are
weakly incomparable.

While our aim is to prove Theorem VI.2.1 – a statement about
$\mathrm{LU\kern-0.50003ptA}$, i.e., avoidance of the _family_ of linearly
universal partial recursive functions – we first establish the case of
avoidance of individual universal partial recursive functions.

######  Theorem VI.2.2.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function,
$\psi_{1}$ and $\psi_{2}$ are universal partial recursive functions, and
$\psi_{3}$ and $\psi_{4}$ are partial recursive functions. Then there exists a
order function $q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ u$ is slow-
growing and

$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2}).$

In order to make use of tools like the Parametrization and Recursion Theorems,
we start by proving the following technical result, in which the instances of
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})$ and
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ are replaced with
$\mathrm{DNR}(p_{1})$ and $\mathrm{DNR}(q\circ u)$, respectively, where
$\mathrm{DNR}$ may be defined with respect to any admissible enumeration.

######  Theorem VI.2.3.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function, and
$\psi_{1}$, $\psi_{2}$ are partial recursive functions. Then there exists an
order function $q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ u$ is slow-
growing and

$\mathrm{DNR}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)\quad\text{and}\quad\mathrm{DNR}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2}).$

Theorem VI.2.3 shows that we can construct our desired order function $q$ in
such a way that we address the (potentially faster-growing) function $q\circ
u$ concurrently, no matter how fast-growing $u$ may be. Within the context of
deriving Theorem VI.2.2, $u$ encapsulates the ‘translation’ from one universal
function to another. This intuition will be helpful later when we examine the
situation of (sufficiently well-behaved) families universal partial recursive
functions in the place of $\psi_{1}$ and $\psi_{2}$ within Theorem VI.2.2,
including in particular the family of linearly universal partial recursive
functions.

###### Proof of Theorem VI.2.2..

Let $\varphi$ be the admissible enumeration with which $\mathrm{DNR}$ is
defined with respect to, and let $\psi$ be its diagonal.

Because $\psi_{1}$ is universal, there exists a total recursive function
$u_{1}\colon\mathbb{N}\to\mathbb{N}$ such that $\psi_{1}\circ u_{1}=\psi$.
$u_{1}$ is unbounded (as $\psi=\psi_{1}\circ u_{1}$ is universal) but not
necessarily nondecreasing, so let $\tilde{u}_{1}$ be defined by
$\tilde{u}_{1}(x)\mathrel{{\vdotdot}{\equal}}\max_{i\leq x}{u_{1}(x)}$. Then
$p_{1}\circ\tilde{u}_{1}$ is an order function such that $p_{1}(x)\leq
p_{1}(\tilde{u}_{1}(x))$ for all $x\in\mathbb{N}$, so

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ\tilde{u}_{1})\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ
u_{1})\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1}).$

If $q$ is found such that
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ\tilde{u}_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)$,
then
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)$.

Likewise, $\psi_{2}$ being universal implies there is a total recursive
function $u_{2}\colon\mathbb{N}\to\mathbb{N}$ such that $\psi_{2}\circ
u_{2}=\psi$. With $\tilde{u}_{2}(x)\mathrel{{\vdotdot}{\equal}}\max_{i\leq
x}{u_{2}(x)}$, for any order function $q$ we have

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ
u\circ\tilde{u}_{2})\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ
u\circ
u_{2})\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u).$

If $q\colon\mathbb{N}\to(1,\infty)$ is found such that
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ
u\circ\tilde{u})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$,
then $\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$.
By potentially replacing $\tilde{u}_{2}$ with
$\tilde{u}_{2}+\operatorname{id}_{\mathbb{N}}$, we may assume without loss of
generality that $\tilde{u}_{2}$ is strictly increasing, so that
$u\circ\tilde{u}_{2}$ is also strictly increasing.

Applying Theorem VI.2.3 to the order functions $p_{1}\circ\tilde{u}_{1}$,
$p_{2}$, and $u\circ\tilde{u}_{2}$ and partial recursive functions $\psi_{3}$,
$\psi_{4}$ yields an order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ\tilde{u}_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)$
and $\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ
u\circ\tilde{u})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$,
which by our above observation is enough to complete the proof. ∎

Consider the special case of Theorem VI.2.3 where $p_{1}=p_{2}=p$ and
$\psi_{1}=\psi_{2}=\psi$ is the diagonal of the admissible enumeration
$\varphi$ with respect to which $\mathrm{DNR}$ is defined. $q$ must be a slow-
growing function which cannot dominate $p$ and also cannot be dominated by
$p$. This suggests an approach to defining $q$ in which $q$ alternates between
two phases, one in which $q$ grows slowly in comparison to $p$ and one in
which $q$ grows fastly in comparison to $p$. To ensure $q\circ u$ is slow-
growing, whenever we enter a slow-growing phase we stay within that phase long
enough to work towards $\tsum\slimits@_{n=0}{q(n)^{-1}}$ diverging.

In fact, our construction of $q$ will alternate between two actions. The first
action involves keeping $q$ constant for a sufficiently long time so that the
bushy tree forcing arguments within $p_{2}$ go through. In the second action,
$q$ makes a sudden jump so that $q$ passes certain watermarks infinitely
often, allowing the bushy tree forcing arguments within $q$ to go through. By
staying constant sufficiently long, we can ensure that $q\circ u$ is slow-
growing.

###### Proof of Theorem VI.2.3..

Suppose $p_{1}$ and $p_{2}$ are order functions and $\psi_{1}$, $\psi_{2}$ are
partial recursive functions. Let $\varphi$ be an admissible enumeration and
let $\psi$ be its diagonal. Let $\langle\Gamma_{i}\rangle_{i\in\mathbb{N}}$ be
an effective enumeration of all partial recursive functions
$\Gamma_{i}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ as in Proposition I.3.22(i), and
assume without loss of generality that if $\Gamma_{i}^{\tau}(n){\downarrow}$
then it does so within $|\tau|$-many steps, so that the predicate
$R(i,\tau,n)\equiv\Gamma_{i}^{\tau}(n){\downarrow}$ is recursive. Given
$X\in\mathbb{N}^{\mathbb{N}}$, $\Gamma_{i}^{X}$ is the partial function
defined by $\Gamma_{i}^{X}(n)\simeq m$ if and only if there exists
$s\in\mathbb{N}$ such that
$\Gamma_{i}^{X{\upharpoonright}\,s}(n){\downarrow}=m$.

###### Step 1: Defining auxiliary functions.

We will define total recursive functions
$\theta_{1}\colon\mathbb{N}\times\mathbb{N}^{2}\to\mathbb{N}$ and
$\theta_{2}\colon\mathbb{N}\times\mathbb{N}^{3}\to\mathbb{N}$ which will be
used in the definition of $q$. In anticipation of using the Recursion Theorem,
one of the arguments of $\theta_{1}$ and $\theta_{2}$ will be reserved for an
index $e$ which will eventually be an index of $q$.

Define the partial recursive function $\chi_{1}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\times\mathbb{N}^{3}\to\mathbb{N}$ so that on input
$\langle\sigma,i,e,x\rangle$, $\chi_{1}$ searches for a finite tree $T$ such
that:

  1. (i)

For every $\tau\in T$ and every $j\leq|\tau|$, $\varphi_{e}(j){\downarrow}$
and $\tau(j)<\varphi_{e}(j)$ when $j<|\tau|$.

  2. (ii)

$T$ is $k$-bushy above $\sigma$ for some $k<\varphi_{e}(|\sigma|)$.

  3. (iii)

$\Gamma_{i-1}^{\tau}(x)$ converges to a common value $j<p_{1}(x)$ for every
leaf $\tau$ of $T$. (For the case of $i=0$, set $\Gamma_{-1}=\Gamma_{0}$.)

$\chi_{1}(\sigma,i,e,x)$ is equal to that common value of
$\Gamma_{i}^{\tau}(x)$ for the first such tree $T$ found, whenever such a tree
exists. $\chi_{1}$ is partial recursive, so by the Parametrization Theorem,
there exists a total recursive function
$\theta_{1}\colon\mathbb{N}\times\mathbb{N}^{2}\to\mathbb{N}$ such that
$\varphi_{\theta_{1}(\sigma,i,e)}(x)\simeq\chi_{1}(\sigma,i,e,x)$ for all
$\sigma\in\mathbb{N}$ and $i,e,x\in\mathbb{N}$.

Similarly, the partial recursive function $\chi_{2}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\times\mathbb{N}^{4}\to\mathbb{N}$ is defined so that on input
$\langle\sigma,i,e,x,N\rangle$, $\chi_{2}$ first attempts to compute
$\varphi_{e}(N)$, followed by verifying that $N\in\operatorname{im}{u}$
(denoting by $n$ the unique element of ${u}^{-1}[\\{N\\}]$), then finds the
least $k>n$ such that $p_{2}(k)\geq(\varphi_{e}(N)+1)\cdot p_{2}(n)$, and
finally searches for a finite tree $T$ such that:

  1. (i)

For every $\tau\in T$ and every $j<|\tau|$, $\tau(j)<p_{2}(j)$.

  2. (ii)

$T$ is $p_{2}(n)$-bushy above $\sigma$.

  3. (iii)

$\Gamma_{i}^{\tau}(x)$ converges to a common value $j<\varphi_{e}(N)$ for
every leaf $\tau$ of $T$.

$\chi_{2}(\sigma,i,e,x,N)$ is equal to that common value of
$\Gamma_{i}^{\tau}(x)$ for the first such tree $T$ found, whenever such a tree
exists. $\theta_{2}\colon\mathbb{N}\times\mathbb{N}^{3}\to\mathbb{N}$ is then
a total recursive function for which
$\varphi_{\theta_{2}(\sigma,i,e,N)}(x)\simeq\chi_{2}(\sigma,i,e,x,N)$ for all
$\sigma\in\mathbb{N}$ and $i,e,x,N\in\mathbb{N}$. We may assume without loss
of generality that $\theta_{2}(\sigma,i,e,N)\geq|\sigma|$ for all
$\sigma\in\mathbb{N}$ and $i,e,N\in\mathbb{N}$.

###### Step 2: Defining $q$.

Having defined $\theta_{1}$ and $\theta_{2}$, we are in a position to define
$q$ by way of a partial recursive function $Q\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{2}\to\mathbb{N}$. To aid in its construction, we
simultaneously define three other partial recursive functions
$s,i,N\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{2}\to\mathbb{N}$ — $s$ takes values in $\\{0,1\\}$,
indicating which type of action we perform next, while $i$ and $N$ keep track
of our progress for one of those two actions. Write
$\overline{\theta}_{1}(e,x)\mathrel{{\vdotdot}{\equal}}\max_{j<x,\sigma\in(\varphi_{e})^{x}}{\theta_{1}(\sigma,j,e)}$,
assuming $\varphi_{e}(j){\downarrow}$ for all $j<x$.

$Q(e,0)$.

Define $Q(e,0)\mathrel{{\vdotdot}{\equal}}3$ and
$s(e,0)=i(e,0)=N(e,0)\mathrel{{\vdotdot}{\equal}}0$.

$Q(e,x)$ ($x>1$).

On input $\langle e,x\rangle$, $Q$ attempts to compute $\varphi_{e}(j)$,
$Q(e,j)$, $s(e,j)$, $i(e,j)$, and $N(e,i(e,j))$ for each $j<x$. If and when it
has done so successfully, the computation proceeds in one of two ways
depending on the value of $s(e,x-1)$.

Case 1: $s(e,x-1)=0$.

Compute
$\overline{\theta}_{1}(e,x)\mathrel{{\vdotdot}{\equal}}\max_{j<x,\sigma\in(\varphi_{e})^{x}}{\theta_{1}(\sigma,j,e)}$,
and then set

$Q(e,x)\mathrel{{\vdotdot}{\equal}}p_{1}(\overline{\theta}_{1}(e,x))\cdot
Q(e,x-1)+Q(e,x-1)+2.$

Additionally set $s(e,x)\mathrel{{\vdotdot}{\equal}}1$ and
$i(e,x)\mathrel{{\vdotdot}{\equal}}i(e,x-1)$.

Case 2: $s(e,x-1)=1$.

Write $i\mathrel{{\vdotdot}{\equal}}i(e,x-1)$ and
$N_{i}\mathrel{{\vdotdot}{\equal}}N(e,i)$. If $N_{i}\notin\operatorname{im}u$,
then $Q(e,x)$, $s(e,x)$, and $i(e,x)$ all diverge. Otherwise, let
$n_{i}\mathrel{{\vdotdot}{\equal}}{u}^{-1}(N_{i})$. As in the definition of
$\chi_{2}$, let $k>n_{i}$ be the least natural number such that
$p_{2}(k)\geq(\varphi_{e}(N_{i})+1)\cdot p_{2}(n_{i})$ ($k$ is defined because
$\varphi_{e}(N_{i}){\downarrow}$ and $N_{i}\in\operatorname{im}{u}$). Let $M$
be the least natural number such that  (I) $M>\max_{\sigma\in
p_{2}^{k}}{{u}(\theta_{2}(\sigma,i,e,N_{i}))}$,  (II)
$M\in\operatorname{im}({u})$,  (III) and
$\tsum\slimits@_{N_{i}<{u}(j)<M}{Q(e,N_{i})^{-1}}\geq 1$.

If the inequality $N_{i}<x<M$ fails, then $Q(e,x)$, $s(e,x)$, and $i(e,x)$ all
diverge. Otherwise:

Subcase 1.

If $x<M-1$, then set $Q(e,x)\mathrel{{\vdotdot}{\equal}}Q(e,x-1)$,
$s(e,x)\mathrel{{\vdotdot}{\equal}}s(e,x-1)$, and
$i(e,x)\mathrel{{\vdotdot}{\equal}}i(e,x-1)$.

Subcase 2.

If $x=M-1$, then set $Q(e,x)\mathrel{{\vdotdot}{\equal}}Q(e,x-1)$,
$s(e,x)\mathrel{{\vdotdot}{\equal}}0$,
$i(e,x)\mathrel{{\vdotdot}{\equal}}i(e,x-1)+1$, and
$N(e,i(e,x))\mathrel{{\vdotdot}{\equal}}M$.

By the Recursion Theorem, there exists an $e\in\mathbb{N}$ such that
$Q(e,x)\simeq\varphi_{e}(x)$ for all $x\in\mathbb{N}$. From the construction
of $Q$, if $Q(e,j)$ is defined for all $j<x$ then $Q(e,x)$ is defined; along
with the fact that $Q(e,0)$ is defined, it follows that $\varphi_{e}$ is a
total recursive function. The construction of $N$ also ensures that
$N(e,i)\in\operatorname{im}u$ for all $i\in\mathbb{N}$. We will write

$\begin{array}[]{c}\begin{array}[]{c c c c
c}q\mathrel{{\vdotdot}{\equal}}\varphi_{e},&s(x)\mathrel{{\vdotdot}{\equal}}s(e,x),&i(x)\mathrel{{\vdotdot}{\equal}}i(e,x),&N_{i}\mathrel{{\vdotdot}{\equal}}N(e,i),&n_{i}\mathrel{{\vdotdot}{\equal}}u^{-1}(N_{i}),\end{array}\vspace{2pt}\\\
\begin{array}[]{c c
c}\theta_{1}(\sigma,i)\mathrel{{\vdotdot}{\equal}}\theta_{1}(\sigma,i,e),&\overline{\theta}_{1}(x)\mathrel{{\vdotdot}{\equal}}\max\limits_{j<x,\sigma\in
q^{x}}{\theta_{1}(\sigma,j,e)},&\theta_{2}(\sigma,i)\mathrel{{\vdotdot}{\equal}}\theta_{2}(\sigma,i,e,N_{i}).\end{array}\end{array}$

Each of these are total recursive functions.

Both $s(x)=0$ and $s(x)=1$ occur for infinitely many $x\in\mathbb{N}$. That
Case 1 ($s(x-1)=0$) occurs infinitely often implies that $q$ is unbounded.
That Case 2 ($s(x-1)=1$) occurs infinitely often implies that $q\circ{u}$ is
slow-growing. In both Case 1 and Case 2, the definition of $Q$ enforces that
$q(x)\leq q(x+1)$ for all $x\in\mathbb{N}$, so $q$ and $q\circ{u}$ are slow-
growing order functions.

###### Step 3: Showing
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$.

We use basic bushy tree forcing. Let $\mathbb{P}$ be the set of all pairs
$\langle\sigma,B\rangle\in q\times\mathcal{P}(q)$ where
$\sigma\neq\langle\rangle$ and $B$ is $k$-small above $\sigma$, $k$-closed,
and upward closed for some $k\leq q(|\sigma|-1)$. $\langle\tau,C\rangle$
_extends_ $\langle\sigma,B\rangle$ if $\sigma\subseteq\tau$ and $B\subseteq
C$. For $i\in\mathbb{N}$, let $\mathcal{D}_{i}$ denote the set of
$\langle\sigma,B\rangle\in\mathbb{P}$ such that for all
$X\in\left\llbracket\sigma\right\rrbracket_{q}\setminus\left\llbracket
B\right\rrbracket_{q}$,
$\Gamma_{i}^{X}\notin\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1})$.

Claim 1.

For each $m$,
$\mathcal{T}_{m}=\\{\langle\sigma,B\rangle\in\mathbb{P}\mid|\sigma|\geq m\\}$
is dense open in $\mathbb{P}$.

###### Proof.

$\mathcal{T}_{m}$ is clearly open in $\mathbb{P}$. To show that
$\mathcal{T}_{m}$ is dense in $\mathbb{P}$, let $C=\\{\tau\in q\mid|\tau|\geq
m\\}$. For any string $\sigma$, $C$ is $k$-big above $\sigma$ if and only if
$k\leq q(|\sigma|)$. In particular, $C$ is $k$-big above $\sigma$ for all
$k\leq q(|\sigma|-1)$.

Suppose $\langle\sigma,B\rangle\in\mathbb{P}$; let $k\leq q(|\sigma|-1)$ be
such that $B$ is $k$-small above $\sigma$ and $k$-closed. If $|\sigma|\geq m$,
then we are done. Otherwise, let $\tau$ be any string in $C\setminus B$
extending $\sigma$. Because $B$ is $k$-closed and $\tau\notin B$, $B$ is
$k$-small above $\tau$. Then $\langle\tau,B\rangle$ is an extension of
$\langle\sigma,B\rangle$ in $\mathcal{T}_{m}$. ∎

Claim 2.

If $\mathcal{G}$ is any filter on $\mathbb{P}$, then for all
$\langle\sigma,B\rangle\in\mathcal{G}$,
$X_{\mathcal{G}}\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@\\{\tau\in
q\mid\exists C\subseteq q(\langle\tau,C\rangle\in\mathcal{G})\\}$ has no
initial segment in $B$.

###### Proof.

Suppose otherwise, so that there is $\tau\in B$ which is an initial segment of
$X_{\mathcal{G}}$. By the definition of $X_{\mathcal{G}}$, there must be a
$\langle\rho^{\prime},C^{\prime}\rangle\in\mathcal{G}$ such that
$\rho^{\prime}$ extends $\tau$. Let $\langle\rho,C\rangle$ be a common
extension of $\langle\rho^{\prime},C^{\prime}\rangle$ and
$\langle\sigma,B\rangle$. Because $B$ is upward-closed, $\rho\in B$. But
$B\subseteq C$, so $\rho\in C$ and hence $C$ is $k$-big above $\rho$ for every
$k$, a contradiction. ∎

Claim 3.

For all $i\in\mathbb{N}$, $\mathcal{D}_{i}$ is dense open in $\mathbb{P}$.

###### Proof.

$\mathcal{D}_{i}$ is clearly open in $\mathbb{P}$, so it must remains to show
that $\mathcal{D}_{i}$ is dense in $\mathbb{P}$.

Suppose $\langle\sigma,B\rangle\in\mathbb{P}$; let $k\leq q(|\sigma|-1)$ be
such that $B$ is $k$-small above $\sigma$. By potentially extending to an
element of $\mathcal{T}_{m}$ for an appropriate $m$, we can assume that
$|\sigma|>i$ and that in the computation of $q(|\sigma|)$, Case 2 occurs. Let
$x=|\sigma|$ and define

$A=\\{\tau\in
q\mid\Gamma_{i}^{\tau}(\theta_{1}(\sigma,i)){\downarrow}<p_{1}(\theta_{1}(\sigma,i))\\}.$

There are two cases:

Case I.

Suppose $A$ is $p_{1}(\theta_{1}(\sigma,i))\cdot q(x-1)$-small above $\sigma$.
Let $c=p_{1}(\theta_{1}(\sigma,i))\cdot q(x-1)+k-1$, so $A\cup B$ is $c$-small
above $\sigma$ by Lemma VI.1.4. Let $C$ be the $c$-closure of $A\cup B$ (note
that although this $c$-closure is taken in $\mathbb{N}$, $A\cup B$ being
$c$-big above $\tau$ implies $\tau\in q$, so $C\subseteq q$). By definition,
$C$ is $c$-small above $\sigma$, $c$-closed, and upward closed.

Since $q(x)=p(\theta_{1}(\sigma,i))\cdot q(x-1)+q(x-1)+2>c$ and $q$ is
nondecreasing, $\\{\tau\in q^{x+1}\mid\sigma\subseteq\tau\\}$ is $c$-big above
$\sigma$. Thus, there is a string $\tau$ in $q^{x+1}\setminus C$ extending
$\sigma$. Because $C$ is $c$-closed, it is $c$-small above $\tau$, and hence
$\langle\tau,C\rangle\in\mathbb{P}$ (here we are also using the fact that $C$
is upward closed). Because $A\subseteq C$,
$\langle\tau,C\rangle\in\mathcal{D}_{i}^{\psi}$ by virtue of $\Gamma^{g}_{i}$
being partial for any
$g\in\left\llbracket\tau\right\rrbracket_{q}\setminus\left\llbracket
C\right\rrbracket_{q}$. Because $B\subseteq C$ and $\sigma\subseteq\tau$,
$\langle\tau,C\rangle$ extends $\langle\sigma,B\rangle$.

Case II.

If $A$ is $p_{1}(\theta_{1}(\sigma,i))\cdot q(x-1)$-big above $\sigma$, then
Lemma VI.1.8(c) implies $\\{\tau\in
q\mid\Gamma^{\tau}_{i}(\theta_{1}(\sigma,i)){\downarrow}=k\\}$ is $q(x-1)$-big
above $\sigma$ for some $k<p_{1}(\theta_{1}(\sigma,i))$. This implies
$\varphi_{\theta_{1}(\sigma,i)}(\theta_{1}(\sigma,i))$ is defined. Let $\tau$
be an extension of $\sigma$ in $q\setminus B$ such that
$\Gamma_{i}^{\tau}(\theta_{1}(\sigma,i))=\varphi_{\theta_{1}(\sigma,i)}(\theta_{1}(\sigma,i))$.
Then $\langle\tau,B\rangle$ is an element of $\mathcal{D}_{i}$ extending
$\langle\sigma,B\rangle$.

∎

Let $B_{\mathrm{A\kern-0.56001ptvoid}^{\psi_{1}}(q)}$ be the set of all
strings in $q$ which cannot be extended to an element of
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$. Let $\sigma_{0}$ be a string of
length $1$ such that $\sigma_{0}(0)\nsimeq\psi_{1}(0)$, if
$\psi_{1}(0){\downarrow}$. $B_{\mathrm{A\kern-0.56001ptvoid}^{\psi_{1}}(q)}$
is $2$-small above $\sigma_{0}$, upward closed, and $2$-closed, so
$\langle\sigma_{0},B_{\mathrm{A\kern-0.56001ptvoid}^{\psi_{1}}(q)}\rangle\in\mathbb{P}$.
Let $\mathcal{G}$ be a filter containing
$\langle\sigma_{0},B_{\mathrm{A\kern-0.56001ptvoid}^{\psi_{1}}(q)}\rangle$
which meets $\mathcal{T}_{m}$ and $\mathcal{D}_{i}$ for all
$m,i\in\mathbb{N}$. Claim 1 shows that $X_{\mathcal{G}}\in\tprod\slimits@{q}$,
Claim 2 shows that
$X_{\mathcal{G}}\in\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$, and Claim 3
shows that $X_{\mathcal{G}}$ computes no element of
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1})$. In other words,

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q).$

###### Step 4: Showing
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ{u})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2})$.

We define a sequence $\langle\sigma_{i},B_{i}\rangle_{i\in\mathbb{N}}$ such
that:

  1. (i)

$\sigma_{i}\in p_{2}^{n_{i}}\setminus B_{i}$.

  2. (ii)

$B_{i}\subseteq p_{2}$ is $p_{2}(n_{i})$-small above $\sigma_{i}$.

  3. (iii)

For all $i\in\mathbb{N}$, $\sigma_{i}\subseteq\sigma_{i+1}$ and
$B_{i}\subseteq B_{i+1}$.

Let $B_{1}=B_{\mathrm{A\kern-0.56001ptvoid}^{\psi_{2}}(p_{2})}$ and
$\sigma_{1}$ an arbitrary element of $p_{2}^{n_{1}}\setminus B_{1}$. (Note
that $p_{2}(1)\geq 2$ and $B_{1}$ is $2$-small above $\sigma_{1}$, so in
particular $p_{2}(1)$-small above $\sigma_{1}$.) Suppose $\sigma_{i},B_{i}$
have been constructed. Let $k$ be as in Case 2 of the construction of $Q$ and
let $\rho$ be an extension of $\sigma_{i}$ in $p_{2}^{k}\setminus B_{i}$
($k\geq n_{i}$, so $p_{2}^{k}$ is $p_{2}(n_{i})$-big above $\sigma_{i}$). For
$j<(q\circ{u})(\theta_{2}(\rho,i))$, let

$A_{j}=\\{\tau\in
p_{2}\mid\Gamma_{i-1}^{\tau}(\theta_{2}(\rho,i)){\downarrow}=j\\}.$

We have two cases, depending upon whether $A_{j}$ is $p_{2}(n_{i})$-big above
$\rho$ for some $j$ or not.

Case 1.

If $A_{j}$ is $p_{2}(n_{i})$-big above $\rho$ for some $j$, then
$\varphi_{\theta_{2}(\rho,i)}(\theta_{2}(\rho,i))$ is defined. In that case,
let $j^{\prime}=\varphi_{\theta_{2}(\rho,i)}(\theta_{2}(\rho,i))$, so there is
a $\tau\in A_{j^{\prime}}\setminus B_{i}$ extending $\rho$ such that

$\Gamma_{i-1}^{\tau}(\theta_{2}(\rho,i))=j^{\prime}=\varphi_{\theta_{2}(\rho,i)}(\theta_{2}(\rho,i)).$

Let $B_{i+1}=B_{i}$ and let $\sigma_{i+1}$ be any extension of $\tau$ in
$p_{2}^{n_{i+1}}\setminus B_{i+1}$.

Case 2.

If $A_{j}$ is $p_{2}(n_{i})$-small above $\rho$ for all $j$, then
$\tbigcup\slimits@_{j}{A_{j}}$ is
$(p_{2}(n_{i})\cdot(q\circ{u})(\theta_{2}(\rho,i))-(q\circ{u})(\theta_{2}(\rho,i))+1)$-small
above $\rho$. Let

$c=p_{2}(n_{i})\cdot((q\circ{u})(\theta_{2}(\rho,i))+1)-(q\circ{u})(\theta_{2}(\rho,i))$

Then $C=\tbigcup\slimits@_{j}{A_{j}}\cup B_{i}$ is $c$-small above $\rho$.

We claim that $(q\circ{u})(n_{i})=(q\circ{u})(\theta_{2}(\rho,i))$. First we
note the inequality $k=|\rho|\leq\theta_{2}(\rho,i)$ by the definition of
$\theta_{2}$, so that $N_{i}<u(k)=u(|\rho|)\leq\theta_{2}(\rho,i)$. By the
definition of $N_{i+1}$, we additionally have $\theta_{2}(\rho,i)<N_{i+1}$.
The definition of $q$ then gives $q(N_{i})=q({u}(\theta_{2}(\rho,i)))$, or
equivalently $(q\circ{u})(n_{i})=(q\circ{u})(\theta_{2}(\rho,i))$.

As a result,

$\displaystyle p_{2}(k)$ $\displaystyle\geq
p_{2}(n_{i})\cdot((q\circ{u})(n_{i})+1)$
$\displaystyle=p_{2}(n_{i})\cdot((q\circ{u})(\theta_{2}(\rho,i))+1)$
$\displaystyle\geq c,$

so that $C$ is $p_{2}(k)$-small above $\rho$. Because $k\leq n_{i+1}$, $C$ is
also $p_{2}(n_{i+1})$-small above $\rho$. Finally, let $B_{i+1}=C$ and let
$\sigma_{i+1}$ be any extension of $\rho$ in $p_{2}^{n_{i+1}}\setminus
B_{i+1}$.

This completes the construction of the sequence
$\langle\sigma_{i},B_{i}\rangle_{i\in\mathbb{N}}$. Let
$Y\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@_{i\in\mathbb{N}}{\sigma_{i}}$.
By construction, $Y\in\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2})$.
Observe that within the above construction, falling into Case 1 at stage $i$
implies $\Gamma_{i}^{Y}$ is not a member of
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$. In other words,

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ{u})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2}).$

This completes the proof.

∎

###  VI.3 Avoidance of Well-Behaved Families of Universal Partial Recursive
Functions

Now we turn to families of universal partial recursive functions, with the
prototypical example being the family of linearly universal partial recursive
functions.

######  Definition VI.3.1 (translation).

If $\psi_{1}$ and $\psi_{2}$ are universal partial recursive functions, then a
_translation_ from $\psi_{1}$ to $\psi_{2}$ is a total recursive function $u$
such that $\psi_{1}\circ u=\psi_{2}$.

######  Definition VI.3.2 (translationally bounded).

Fix a universal partial recursive function $\psi_{0}$. We say that a family
$\mathcal{C}\subseteq\mathbb{N}^{\mathbb{N}}$ of universal partial recursive
functions is _translationally bounded_ if there exists an order function
$U\colon\mathbb{N}\to\mathbb{N}$ such that for every $\psi\in\mathcal{C}$
there is a translation from $\psi$ to $\psi_{0}$ which is dominated by $U$.

######  Remark VI.3.3.

Being translationally bounded from above does not depend on the choice of
universal partial recursive function $\psi_{0}$: Suppose $\mathcal{C}$ is
translationally bounded with respect to $\psi_{0}$, witnessed by $U$, and
$\psi_{1}$ is another universal partial recursive function. Let $v$ be a
translation from $\psi_{1}$ to $\psi_{0}$, and let $\overline{v}$ be the order
function defined by $\overline{v}(x)\mathrel{{\vdotdot}{\equal}}\max_{i\leq
x}{v(i)}$. Then $U\circ\overline{v}$ witnesses $\mathcal{C}$ being
translationally bounded with respect to $\psi_{1}$.

######  Example VI.3.4.

The family $\mathcal{LU}$ of linearly universal partial recursive functions is
translationally bounded, witnessed by the order function $U=\lambda n.n^{2}$.
The same function also shows the family of the diagonals of linear admissible
enumerations of the partial recursive functions is also translationally
bounded.

######  Example VI.3.5.

Suppose $\mathcal{F}$ is a set of total recursive functions such that there is
a recursive function $U$ dominating every member of $\mathcal{F}$. Temporarily
say that a universal partial recursive function $\psi$ is _$\mathcal{F}$
-universal_ if for every partial recursive function $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ there exists a $u\in\mathcal{F}$ such that
$\psi\circ u=\theta$. Then the family $\mathcal{C}$ of all
$\mathcal{F}$-universal partial recursive functions is translationally
bounded, witnessed by $U$.

Particular examples include the set of linear functions, the set of recursive
linearly bounded functions, or the set of primitive recursive functions.

######  Lemma VI.3.6.

Suppose $\mathcal{C}$ is a nonempty family of universal partial recursive
functions which is translationally bounded, witnessed by the order function
$U\colon\mathbb{N}\to\mathbb{N}$. Then for all order functions
$p\colon\mathbb{N}\to(1,\infty)$ and all universal partial recursive functions
$\psi_{0}$, $\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(p\circ
U)\mathrel{{}_{\mathrm{w}}}\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}}(p)$.

###### Proof.

Let $X$ be an element of $\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}}(p)$, so
that there is a $\psi\in\mathcal{C}$ such that
$X\in\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$. By hypothesis, there exists a
total recursive function $u\colon\mathbb{N}\to\mathbb{N}$ such that $\psi\circ
u=\psi_{0}$ and which is dominated by $U$. Then
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(p\circ
U)\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(p\circ
u)\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$, so $X$
computes a member of $\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(p\circ U)$. ∎

######  Theorem VI.3.7.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function,
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are nonempty families of universal
partial recursive functions which are each translationally bounded, and
$\psi_{1}$ and $\psi_{2}$ are partial recursive functions. Then there exists
an order function $q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ u$ is
slow-growing and for which

$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2}).$

###### Proof.

Let $\psi$ be the diagonal of an acceptable enumeration of the partial
recursive functions. By hypothesis, there are order functions
$U_{1}\colon\mathbb{N}\to\mathbb{N}$ and $U_{2}\colon\mathbb{N}\to\mathbb{N}$
witnessing the fact that $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are
translationally bounded, respectively. Applying Theorem VI.2.3 to $p_{1}\circ
U_{1}$, $p_{2}$, and $u\circ U_{2}$ yields an order function
$q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ u\circ U_{2}$ is slow-
growing (and hence $q\circ u$ as well),
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ
U_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$,
and $\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ u\circ
U_{2})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2})$.
By Lemma VI.3.6, $\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ
U_{1})\mathrel{{}_{\mathrm{w}}}\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{1}}(p_{1})$
and $\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ u\circ
U_{2})\mathrel{{}_{\mathrm{w}}}\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{2}}(q\circ
u)$, so $\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{1}\circ
U_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$
implies
$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(q)$
and $\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ u\circ
U_{2})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2})$
implies $\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(p_{2})$.
∎

Theorem VI.2.1 is then an easy consequence:

###### Proof of Theorem VI.2.1..

Let $p_{1}$ and $p_{2}$ be order functions,
$u\mathrel{{\vdotdot}{\equal}}\operatorname{id}_{\mathbb{N}}$,
$\mathcal{C}_{1}=\mathcal{C}_{2}\mathrel{{\vdotdot}{\equal}}\mathcal{LU}$, and
$\psi_{1}=\psi_{2}\mathrel{{\vdotdot}{\equal}}\psi$ any linearly universal
partial recursive function. By Theorem VI.3.7, there is a slow-growing order
function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$
and
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{2})$.
Since
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)\subseteq\mathrm{LU\kern-0.50003ptA}(q)$
and
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p_{2})\subseteq\mathrm{LU\kern-0.50003ptA}(p_{2})$,
we find that
$\mathrm{LU\kern-0.50003ptA}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(q)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{LU\kern-0.50003ptA}(p_{2})$.
∎

###  VI.4 Implications for $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$

Theorem VI.2.1 allows us to make several deductions concerning
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$. The first is that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ is not of deep degree:

######  Theorem VI.4.1.

$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ is not of deep degree.

###### Proof.

Suppose for the sake of a contradiction that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ is weakly equivalent to a deep
r.b. $\Pi^{0}_{1}$ class $P$. We may assume without loss of generality that
$P\subseteq\\{0,1\\}^{\mathbb{N}}$. Because $P$ is deep, taking the inverse of
a modulus of depth for $P$ gives us an order function
$r\colon\mathbb{N}\to\mathbb{N}$ such that
$\mathbf{M}(P{\upharpoonright}\,n)\leq 2^{-r(n)}$ for all $n\in\mathbb{N}$. In
particular, $\mathbf{M}(X{\upharpoonright}\,n)\leq 2^{-r(n)}$ for every $X\in
P$ and $n\in\mathbb{N}$, or equivalently
$\operatorname{KA}(X{\upharpoonright}\,n)\geq r(n)$ for every $X\in P$ and
$n\in\mathbb{N}$, i.e., every $X\in P$ is strongly $r$-random. Thus, every
$X\in P$ is $r$-random, so $P\subseteq\mathrm{COMPLEX}(r)$ and hence
$\mathrm{COMPLEX}(r)\mathrel{{}_{\mathrm{s}}}P$. Theorem III.1.1 shows there
exists a fast-growing order function $p\colon\mathbb{N}\to(1,\infty)$ such
that
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(r)$.
Applying Theorem VI.2.1 yields a slow-growing order function
$q\colon\mathbb{N}\to(1,\infty)$ such that $\mathrm{LU\kern-0.50003ptA}(p)$
and $\mathrm{LU\kern-0.50003ptA}(q)$ are weakly incomparable. But
$\mathrm{LU\kern-0.50003ptA}(q)\subseteq\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$
and hence

$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(r)\mathrel{{}_{\mathrm{s}}}P\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(q)$

giving a contradiction. ∎

Likewise, we can show that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$
for every slow-growing order function $q$:

######  Theorem VI.4.2.

There is no order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.

###### Proof.

Suppose for the sake of a contradiction that
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.
By Theorem VI.2.1, there exists a slow-growing order function
$p\colon\mathbb{N}\to(1,\infty)$ such that $\mathrm{LU\kern-0.50003ptA}(p)$
and $\mathrm{LU\kern-0.50003ptA}(q)$ are weakly incomparable. But $p$ being
slow-growing implies
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$,
a contradiction. ∎

Similarly, we can show that
$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$.

######  Theorem VI.4.3.

$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$.

###### Proof.

For each rational $\delta\in(0,1)$,
$\mathrm{COMPLEX}(\delta)\mathrel{{}_{\mathrm{s}}}\mathrm{SC}(\delta)$. Since
$\sqrt{n}\leq\delta\cdot n$ for almost all $n$, it follows that
$\mathrm{COMPLEX}(\lambda
n.\sqrt{n})\mathrel{{}_{\mathrm{w}}}\mathrm{SC}(\delta)$ for all rational
$\delta\in(0,1)$, so $\mathrm{COMPLEX}(\lambda
n.\sqrt{n})\mathrel{{}_{\mathrm{w}}}\mathrm{SC}$. By Corollary III.1.4 there
exists a fast-growing order function $p\colon\mathbb{N}\to(1,\infty)$ such
that
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(\lambda
n.\sqrt{n})$. Theorem VI.2.1 implies there is a slow-growing order function
$q\colon\mathbb{N}\to(1,\infty)$ such that $\mathrm{LU\kern-0.50003ptA}(p)$
and $\mathrm{LU\kern-0.50003ptA}(q)$ are weakly incomparable. Thus, if
$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$,
then we would have

$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(\lambda
n.\sqrt{n})\mathrel{{}_{\mathrm{w}}}\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q),$

yielding a contradiction. ∎

######  Corollary VI.4.4.

There exists a slow-growing order function $q\colon\mathbb{N}\to(1,\infty)$
such that
$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.

###  VI.5 Replacing Slow-Growing with Depth

The proof of Proposition II.2.2 produced admissible enumerations $\varphi$ and
$\tilde{\varphi}$ such that $\mathrm{DNR}^{(1)}_{\lambda
n.2^{n}}\mathrel{{}_{\mathrm{s}}}\mathrm{DNR}^{(2)}_{\lambda x.x}$, where
$\mathrm{DNR}^{(1)}$ is $\mathrm{DNR}$ defined with respect to $\varphi$ and
$\mathrm{DNR}^{(2)}$ is $\mathrm{DNR}$ defined with respect to
$\tilde{\varphi}$. For this reason, the implications of $q$ being ‘slow-
growing’ on the weak degree of $\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$ are
dependent on the choice of $\psi$. In the case where $\psi$ is linearly
universal partial recursive, $q$ is slow-growing if and only if
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$ is a deep r.b. $\Pi^{0}_{1}$ class.
With that motivation in mind, we strengthen Theorem VI.2.2, with the depth of
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ replacing slow-growing.

######  Theorem VI.5.1.

Suppose $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$ are order functions,
$u\colon\mathbb{N}\to\mathbb{N}$ is a strictly increasing order function,
$\psi_{1}$ and $\psi_{2}$ are universal partial recursive functions, and
$\psi_{3}$ and $\psi_{4}$ are partial recursive functions. Then there exists a
order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ is of deep degree and

$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)\quad\text{and}\quad\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2}).$

Requiring that $\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ is deep is
a stronger condition than simply requiring that $q\circ u$ be slow-growing.

######  Proposition VI.5.2.

Suppose $\psi$ is a universal partial recursive function and
$q\colon\mathbb{N}\to(1,\infty)$ is an order function. If
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$ is of deep degree, then $q$ is slow-
growing.

A benefit of working with linearly universal partial recursive functions
rather than the diagonals of linear admissible enumerations is that if $\psi$
is linearly universal and $\tilde{\psi}$ is univeral, then we may take the
translation $u$ from $\psi$ to $\tilde{\psi}$ to be strictly increasing.
Moreover, Lemma II.4.20 showed that composition with a linear map does not
affect whether an order function is fast-growing or slow-growing.

###### Proof of Proposition VI.5.2..

Suppose $\psi_{0}$ is a linearly universal partial recursive function and
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)$ is of deep degree. There are
$a,b\in\mathbb{N}$ such that $\psi_{0}(ax+b)\simeq\psi(x)$ for all
$x\in\mathbb{N}$, so let $u\colon\mathbb{N}\to\mathbb{N}$ be defined by
$u(x)\mathrel{{\vdotdot}{\equal}}ax+b$ for $x\in\mathbb{N}$. Then
$\psi_{0}\circ u=\psi$. Because $\psi$ is universal, $a$ must be nonzero
(otherwise, $\psi$ would either be constant or undefined everywhere depending
on whether $\psi_{0}(b)$ converges or diverges, respectively). $u$ is hence a
strictly increasing order function.

We extend $q$ and $u$ to real-valued functions
$\overline{q}\colon{[0,\infty)}\to(1,\infty)$ and
$\overline{u}\colon{[0,\infty)}\to{[0,\infty)}$, respectively, by letting
$\overline{q}$ be linear between $\langle x,q(x)\rangle$ and $\langle
x+1,q(x+1)\rangle$ for all $x\in\mathbb{N}$ and likewise with $\overline{u}$.
To be exact, we define

$\displaystyle\overline{q}(x)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}(q(\lfloor x\rfloor+1)-q(\lfloor
x\rfloor))(x-\lfloor x\rfloor)+q(\lfloor x\rfloor),$
$\displaystyle\overline{u}(x)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}(u(\lfloor x\rfloor+1)-u(\lfloor
x\rfloor))(x-\lfloor x\rfloor)+u(\lfloor x\rfloor).$

$\overline{u}$ is strictly increasing, so its inverse
$\overline{u}^{-1}\colon[b,\infty)\to[0,\infty)$ is defined. Finally, define
$\tilde{q}\colon\mathbb{N}\to(1,\infty)$ by

$\tilde{q}(x)\mathrel{{\vdotdot}{\equal}}\lfloor\overline{q}(\overline{u}^{-1}(x))\rfloor$

for all $x\in\mathbb{N}$. $\tilde{q}\circ u$ is dominated by $q$, so
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)\mathrel{{}_{\mathrm{w}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(\tilde{q})$.

Proposition II.4.19 implies
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(\tilde{q})$ is of deep degree, so
Theorem II.4.9 implies $\tilde{q}$ must be slow-growing. $\overline{u}^{-1}$
is a linear map, so $\tilde{q}$ being slow-growing implies
$\tilde{q}\circ\overline{u}$ is also slow-growing by Lemma II.4.20. $q$ is
dominated by $\tilde{q}\circ\overline{u}+1$, so $q$ is slow-growing as well. ∎

###### Proof of Theorem VI.5.1..

Let $\psi_{0}$ be a linearly universal partial recursive function, let
$\varphi$ be the admissible enumeration corresponding to $\psi_{0}$ as in
Section II.2.2, and let $\psi$ be the diagonal of $\varphi$. Define
$\mathrm{DNR}$ with respect to $\varphi$ (i.e., so that
$\mathrm{DNR}=\mathrm{A\kern-0.80002ptvoid}^{\psi}$). Let
$v\colon\mathbb{N}\to\mathbb{N}$ be a translation from $\psi_{2}$ to $\psi$
and let $\tilde{v}\colon\mathbb{N}\to\mathbb{N}$ be a strictly increasing
order function dominating $v$ (e.g.,
$\tilde{v}(x)\mathrel{{\vdotdot}{\equal}}\max-{i\leq x}{v(i)}+x$ for
$x\in\mathbb{N}$).

Theorem VI.2.2 shows there is an order function
$q\colon\mathbb{N}\to(1,\infty)$ such that $q\circ(u\circ\tilde{v})$ is slow-
growing,
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{1}}(p_{1})\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{3}}(q)$,
and
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ(u\circ\tilde{v}))\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$.
Because $q\circ(u\circ\tilde{v})$ is slow-growing and $\psi$ is linearly
universal, it follows that
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ(u\circ\tilde{v}))$ is deep. Using
Proposition II.4.16 and observing that

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ(u\circ\tilde{v}))\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ(u\circ
v))=\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}\circ v}((q\circ u)\circ
v)\mathrel{{}_{\mathrm{s}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$

shows $\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ u)$ is deep.
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(q\circ(u\circ\tilde{v}))\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$
implies $\mathrm{A\kern-0.80002ptvoid}^{\psi_{2}}(q\circ
u)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathrm{A\kern-0.80002ptvoid}^{\psi_{4}}(p_{2})$,
so we have found the desired $q$. ∎

###  VI.6 Open Problems

Although Theorem VI.2.1 significantly expands our understanding of the
relationships between the fast and slow-growing $\mathrm{LU\kern-0.50003ptA}$
hierarchies as well as the structure of the slow-growing
$\mathrm{LU\kern-0.50003ptA}$ hierarchy itself, there remain many open
problems concerning these two subjects.

For example, Theorem VI.2.1 shows that to each order function $p$ there is a
$q$ such that $\mathrm{LU\kern-0.50003ptA}(p)$ and
$\mathrm{LU\kern-0.50003ptA}(q)$ are weakly incomparable, and hence we must
have $p\mathrel{{}_{\mathrm{dom}}}q$ and $q\mathrel{{}_{\mathrm{dom}}}p$, but
what more can be said?

######  Question VI.6.1.

Given an order function $p\colon\mathbb{N}\to(1,\infty)$, what can be said
about how the growth rates of the slow-growing order functions
$q\colon\mathbb{N}\to(1,\infty)$ for which $\mathrm{LU\kern-0.50003ptA}(p)$
and $\mathrm{LU\kern-0.50003ptA}(q)$ are weakly incomparable compare to the
growth rate of $p$? In particular, for the $q$ defined in the proof of Theorem
VI.2.1 alternates between staying constant and making large jumps, but can we
quantify the lengths of those constant periods or the size of those jumps?

Although Theorem VI.4.2 shows that there is no slow-growing order function $q$
for which
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$,
it does not eliminate the possibility that there exist slow-growing order
functions $q$ for which
$\mathop{\deg_{\mathrm{w}}}(\mathrm{LU\kern-0.50003ptA}(q))$ is minimal among
the weak degrees of the slow-growing $\mathrm{LU\kern-0.50003ptA}$ hierarchy.

######  Question VI.6.2.

Given a slow-growing order function $q\colon\mathbb{N}\to(1,\infty)$, does
there exist a slow-growing order function $q^{+}\colon\mathbb{N}\to(1,\infty)$
such that
$\mathrm{LU\kern-0.50003ptA}(q^{+})\mathrel{<_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$?
If so, can we take $q^{+}$ so that $q\mathrel{{}_{\mathrm{dom}}}q^{+}$, and if
that is true, can we quantify how much faster-growing $q^{+}$ must be than $q$
for
$\mathrm{LU\kern-0.50003ptA}(q^{+})\mathrel{<_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$
to hold?

A related question which would address Question VI.6.2 if answered affirmative
is the following:

######  Question VI.6.3.

Given slow-growing order functions $p_{1}\colon\mathbb{N}\to(1,\infty)$ and
$p_{2}\colon\mathbb{N}\to(1,\infty)$, is there a slow-growing order function
$q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(p_{1})\cup\mathrm{LU\kern-0.50003ptA}(p_{2})$?

An affirmative answer to Question VI.6.3 would provide an affirmative answer
to the first half of Question VI.6.2 thanks to Theorem VI.2.1. In Question
VI.6.3, we cannot add the requirement that $q$ dominate both $p_{1}$ and
$p_{2}$, as there exist slow-growing order functions $p_{1}$ and $p_{2}$ such
that $\max\\{p_{1},p_{2}\\}$ is fast-growing.

A positive answer to Question VI.6.3 for
$p_{1}=\operatorname{id}_{\mathbb{N}}$:

######  Proposition VI.6.4.

Suppose $p$ is a slow-growing order function. Then There exists a slow-growing
order function $q$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(p)\cup\mathrm{LU\kern-0.50003ptA}(\lambda
n.n)$.

###### Proof.

It suffices to show that
$q\mathrel{{\vdotdot}{\equal}}\max\\{p,\operatorname{id}_{\mathbb{N}}\\}$ is
slow-growing. Define $A\mathrel{{\vdotdot}{\equal}}\\{n\in\mathbb{N}\mid
p(n)\leq n\\}$. If $A$ is finite, then
$\operatorname{id}_{\mathbb{N}}\mathrel{{}_{\mathrm{dom}}}p$, so
$\max\\{p(n),n\\}=p(n)$ for almost all $n$, hence $q$ is slow-growing. So
suppose $A$ is infinite. Given $n\in A$, let $m$ be maximal such that
$2^{m}\leq n$, so that $p(2^{m})\leq p(n)\leq n\leq 2^{m+1}$. Thus,
$2^{m}\cdot\frac{1}{p(2^{m})}\geq\frac{1}{2}$. It follows that
$\tsum\slimits@_{m=0}{2^{m}\cdot\frac{1}{\max\\{p(2^{m}),2^{m}\\}}}=\infty$.
By the Cauchy Condensation Test, this implies
$\tsum\slimits@_{n=0}{q(n)^{-1}}=\infty$. ∎

######  Corollary VI.6.5.

There exists a slow-growing order function $q$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{<_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(\lambda
n.n)$.

###### Proof.

By either Theorem VI.2.1 or combining [16, Theorem 3.11] and Lemma II.3.16,
there exists a slow-growing order function $p$ such that
$\mathrm{LU\kern-0.50003ptA}(p)$ is weakly incomparable with
$\mathrm{LU\kern-0.50003ptA}(\lambda n.n)$. By Proposition VI.6.4, there is a
slow-growing $q$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(p)\cup\mathrm{LU\kern-0.50003ptA}(\lambda
n.n)$, hence
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{<_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(\operatorname{id}_{\mathbb{N}})$.
∎

Theorem VI.4.3 suggests the following question:

######  Question VI.6.6.

Can we give a natural and specific slow-growing function
$q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$?

##  Chapter VII Structure of the Deep Region of $\mathcal{E}_{\mathrm{w}}$

Two results stated in Section II.4 that gave some idea of the structure of the
collection of deep degrees in $\mathcal{E}_{\mathrm{w}}$ were Proposition
II.4.19, which showed that the collection forms a filter in
$\langle\mathcal{E}_{\mathrm{w}}\rangle$, and Proposition II.4.22, which shows
that no difference random computes a member of any representative of a deep
degree. The goal of this chapter is to examine the structure of the filter of
deep degrees further. Our main goal is to prove the following main theorem.

######  Theorem VII.0.1.

Define

$\displaystyle\mathscr{F}_{\mathrm{deep}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\text{$\mathbf{p}$
a deep degree}\\}.$ $\displaystyle\mathscr{F}_{\mathrm{pseudo}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\text{$\mathbf{p}=\inf\mathcal{C}$
for some $\mathcal{C}\subseteq\mathscr{F}_{\mathrm{deep}}$}\\}.$
$\displaystyle\mathscr{F}_{\mathrm{diff}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\forall
P\in\mathbf{p}\forall X\in\mathsf{MLR}\,(\exists Y\in
P\,(Y\mathrel{{}_{\mathrm{T}}}X)\to(0^{\prime}\mathrel{{}_{\mathrm{T}}}0^{\prime}))\\}.$

Then $\mathscr{F}_{\mathrm{pseudo}}$ is a principal filter while
$\mathscr{F}_{\mathrm{deep}}$ and $\mathscr{F}_{\mathrm{diff}}$ are
nonprincipal filters. Consequently,
$\mathscr{F}_{\mathrm{deep}}\mathrel{\ooalign{\hss\raise
1.29167pt\hbox{$\subset$}\hss\cr\kern
0.86108pt\raise-2.15277pt\hbox{\scalebox{0.7}{$\mathrel{\ooalign{\hss\hbox{\scalebox{1.4}{$-$}}\hss\cr\kern
0.86108pt\raise-0.43057pt\hbox{\rotatebox{45.0}{$-$}}}}$}}}}\mathscr{F}_{\mathrm{pseudo}}\mathrel{\ooalign{\hss\raise
1.29167pt\hbox{$\subset$}\hss\cr\kern
0.86108pt\raise-2.15277pt\hbox{\scalebox{0.7}{$\mathrel{\ooalign{\hss\hbox{\scalebox{1.4}{$-$}}\hss\cr\kern
0.86108pt\raise-0.43057pt\hbox{\rotatebox{45.0}{$-$}}}}$}}}}\mathscr{F}_{\mathrm{diff}}$.

In Section VII.1, we show that the infimum of the collection of deep degrees
$\mathop{\deg_{\mathrm{w}}}(L)$ lies in $\mathcal{E}_{\mathrm{w}}$ but is not
a deep degree itself, showing the filter of deep degrees is nonprincipal.

######  Proposition VII.1.1.

The union $L$ of all deep $\Pi^{0}_{1}$ classes is $\Sigma^{0}_{3}$.
Consequently, $\mathop{\deg_{\mathrm{w}}}(L)\in\mathcal{E}_{\mathrm{w}}$.

######  Theorem VII.1.2.

$\mathop{\deg_{\mathrm{w}}}(L)$ is not a deep degree in
$\mathcal{E}_{\mathrm{w}}$.

In Section VII.2, we define the collection of _pseudo_ -deep degrees in
$\mathcal{E}_{\mathrm{w}}$ and characterize it as the principal filter
generated by $\mathop{\deg_{\mathrm{w}}}(L)$.

######  Theorem VII.2.4.

$\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\text{$\mathbf{p}$ pseudo-
deep}\\}$ is equal to the principal filter generated by
$\mathop{\deg_{\mathrm{w}}}(L)$ in
$\langle\mathcal{E}_{\mathrm{w}},\leq\rangle$.

In Section VII.3, we show that the filters of deep degrees and pseudo-deep
degrees cannot be characterized by the property that no difference random
computes a member of any representative of those degrees.

######  Theorem VII.3.1.

There exists a $\Pi^{0}_{1}$ class $P$ which is not of pseudo-deep degree but
for which no difference random computes an element of $P$.

###  VII.1 The infimum of all deep degrees

An important observation about the collection of deep degrees is that its
infimum is in $\mathcal{E}_{\mathrm{w}}$.

######  Proposition VII.1.1.

The union $L$ of all deep $\Pi^{0}_{1}$ classes is $\Sigma^{0}_{3}$.
Consequently, $\mathop{\deg_{\mathrm{w}}}(L)\in\mathcal{E}_{\mathrm{w}}$.

###### Proof.

Let $\mathbf{M}$ be a fixed universal left r.e. continuous semimeasure on
$\mathbb{N}$, and let the map $\langle
s,\sigma\rangle\mapsto\mathbf{M}_{s}(\sigma)$ realize the left recursive
enumerability of $\mathbf{M}$, i.e., it is a recursive function
$\mathbb{N}\times\mathbb{N}\to\mathbb{Q}$ such that
$\langle\mathbf{M}_{s}(\sigma)\rangle_{s\in\mathbb{N}}$ converges
monotonically to $\mathbf{M}(\sigma)$ from below for each
$\sigma\in\mathbb{N}$. Given $e,s\in\mathbb{N}$, let
$P_{e,s}\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\varphi_{e,s}^{X{\upharpoonright}\,s}(0){\uparrow}\\}$;
$\langle P_{e,s}\rangle_{s\in\mathbb{N}}$ is a sequence of uniformly recursive
subsets whose intersection is $P_{e}$.

Claim 1.

The predicate $\\{\langle
e,m,q\rangle\mid\mathbf{M}(P_{e}{\upharpoonright}\,m)\leq q\\}$ is a
$\Pi^{0}_{2}$ subset of $\mathbb{N}^{2}\times\mathbb{Q}_{\geq 0}$.

###### Proof.

The predicate $\\{\langle
e,m,q,s\rangle\mid\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)\leq q\\}$ is
recursive, so it suffices to show that

$\mathbf{M}(P_{e}{\upharpoonright}\,m)\leq q\iff\forall t\exists
s\,(t<s\wedge\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)\leq q).$

This follows essentially from the observation that the sequence
$\langle\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)\rangle_{s\in\mathbb{N}}$
is eventually nondecreasing for all $e,m\in\mathbb{N}$.

In the forward direction, suppose $\mathbf{M}(P_{e}{\upharpoonright}\,m)\leq
q$. $P_{e}{\upharpoonright}\,m$ is a finite set equal to
$\tbigcap\slimits@_{s\in\mathbb{N}}{P_{e,s}}$, so there exists an
$t\in\mathbb{N}$ such that
$P_{e,s}{\upharpoonright}\,m=P_{e}{\upharpoonright}\,m$ for all $s>t$. Thus,
there are arbitrarily large $s$ such that
$\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)\leq\mathbf{M}_{s}(P_{e}{\upharpoonright}\,m)\leq
q$.

In the opposite direction, assume $\forall t\exists
s\,(t<s\wedge\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)\leq q)$ and suppose
for the sake of a contradiction that
$\mathbf{M}(P_{e}{\upharpoonright}\,m)>q$. Let $t$ be large enough so that
$P_{e,s}{\upharpoonright}\,m=P_{e}{\upharpoonright}\,m$ and
$\mathbf{M}_{s}(P_{e}{\upharpoonright}\,m)>q$ for all $s>t$. But then for all
$s>t$ we have $\mathbf{M}_{s}(P_{e,s}{\upharpoonright}\,m)>q$, contradicting
our assumption. Thus, $\mathbf{M}(P_{e}{\upharpoonright}\,m)\leq q$ is a
$\Pi^{0}_{2}$ subset of $\mathbb{N}^{2}\times\mathbb{Q}$. ∎

Claim 2.

The predicate $\\{i\in\mathbb{N}\mid\text{$\varphi_{i}$ is total}\\}$ is a
$\Pi^{0}_{2}$ subset of $\mathbb{N}$.

###### Proof.

$\varphi_{i}$ being total is equivalent to $\forall n\exists
s\,\varphi_{i,s}(n){\downarrow}$. ∎

Claim 3.

The predicate $\\{e\in\mathbb{N}\mid\text{$P_{e}$ is deep}\\}$ is a
$\Sigma^{0}_{3}$ subset of $\mathbb{N}$.

###### Proof.

$P_{e}$ is deep if and only if $\exists i((\text{$\varphi_{i}$ is
total})\wedge\forall n(\mathbf{M}(P_{e}{\upharpoonright}\,\varphi_{i}(n))\leq
2^{-n}))$. By Claim 1, this is $\Sigma^{0}_{3}$. ∎

Finally,

$\displaystyle L$ $\displaystyle=\tbigcup\slimits@\\{P_{e}\mid\text{$P_{e}$ is
deep}\\}$ $\displaystyle=\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\exists
e((\text{$P_{e}$ is deep})\wedge X\in P_{e})\\}$

shows $L$ is $\Sigma^{0}_{3}$. Since $L$ contains a nonempty $\Pi^{0}_{1}$
class, the  (Embedding Lemma). implies
$\mathop{\deg_{\mathrm{w}}}(L)\in\mathcal{E}_{\mathrm{w}}$. ∎

That $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ (Theorem VI.4.1) is not of
deep degree shows that $L$ is not of deep degree, further clarifying the
structure of the filter of deep degrees in $\mathcal{E}_{\mathrm{w}}$:

######  Theorem VII.1.2.

$\mathop{\deg_{\mathrm{w}}}(L)$ is not a deep degree in
$\mathcal{E}_{\mathrm{w}}$.

###### Proof.

Suppose for the sake of a contradiction that $\mathop{\deg_{\mathrm{w}}}(L)$
is a deep degree in $\mathcal{E}_{\mathrm{w}}$. Then

$\displaystyle\mathop{\deg_{\mathrm{w}}}(L)$
$\displaystyle=\inf\\{\mathop{\deg_{\mathrm{w}}}(P)\mid\text{$P\subseteq\\{0,1\\}^{\mathbb{N}}$
is nonempty, deep}\\}$
$\displaystyle\leq\inf\\{\mathop{\deg_{\mathrm{w}}}(\mathrm{LU\kern-0.50003ptA}(p))\mid\text{$p$
slow-growing order function}\\}$
$\displaystyle=\mathop{\deg_{\mathrm{w}}}(\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}).$

Because $\mathop{\deg_{\mathrm{w}}}(L)$ is a deep degree in
$\mathcal{E}_{\mathrm{w}}$, Proposition II.4.19 shows that
$\mathop{\deg_{\mathrm{w}}}(\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}})$ is a
deep degree in $\mathcal{E}_{\mathrm{w}}$, contradicting Theorem VI.4.1. ∎

######  Corollary VII.1.3.

The filter of deep degrees in $\mathcal{E}_{\mathrm{w}}$ is nonprincipal.

######  Corollary VII.1.4.

For any deep degree $\mathbf{p}\in\mathcal{E}_{\mathrm{w}}$, there exists a
deep degree $\mathbf{q}\in\mathcal{E}_{\mathrm{w}}$ such that
$\mathbf{q}<\mathbf{p}$.

###  VII.2 The Filter of Pseudo-Deep Degrees

Motivated by $L$, $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$, and
$\mathrm{SC}$, we define:

######  Definition VII.2.1 (pseudo-deep degree in $\mathcal{E}_{\mathrm{w}}$).

A weak degree $\mathbf{p}\in\mathcal{E}_{\mathrm{w}}$ is a _pseudo-deep degree
(in $\mathcal{E}_{\mathrm{w}}$)_ if $\mathbf{p}$ is an infimum of deep degrees
in $\mathcal{E}_{\mathrm{w}}$, or equivalently that there is a collection
$\mathcal{C}$ of deep $\Pi^{0}_{1}$ classes such that
$\mathbf{p}=\mathop{\deg_{\mathrm{w}}}(\tbigcup\slimits@{\mathcal{C}})$.

$P\subseteq\mathbb{N}^{\mathbb{N}}$ is _of pseudo-deep degree_ if
$\mathop{\deg_{\mathrm{w}}}(P)$ is a pseudo-deep degree in
$\mathcal{E}_{\mathrm{w}}$.

Proposition II.4.22 continues to hold for $P\subseteq\mathbb{N}^{\mathbb{N}}$
of pseudo-deep degree.

######  Proposition VII.2.2.

Suppose $P\subseteq\mathbb{N}^{\mathbb{N}}$ is of pseudo-deep degree. If
$X\in\\{0,1\\}^{\mathbb{N}}$ is difference random, then $X$ computes no member
of $P$.

###### Proof.

Because $P$ is of pseudo-deep degree, there is a collection $\mathcal{C}$ of
deep $\Pi^{0}_{1}$ classes such that
$P\mathrel{{}_{\mathrm{w}}}\tbigcup\slimits@{\mathcal{C}}$. If
$Y\mathrel{{}_{\mathrm{T}}}X$ for some $Y\in P$, then the fact that
$P\mathrel{{}_{\mathrm{w}}}\tbigcup\slimits@{\mathcal{C}}$ implies there is a
$Q\in\mathcal{C}$ and a $Z\in Q$ such that
$Z\mathrel{{}_{\mathrm{T}}}Y\mathrel{{}_{\mathrm{T}}}X$, contradicting Theorem
II.4.11. ∎

######  Notation VII.2.3.

Let

$\displaystyle\mathscr{F}_{\mathrm{deep}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\text{$\mathbf{p}$
is a deep degree}\\},$ $\displaystyle\mathscr{F}_{\mathrm{pseudo}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\mathbf{p}\in\mathcal{E}_{\mathrm{w}}\mid\text{$\mathbf{p}$
is a pseudo-deep degree}\\}.$

Just as $\mathscr{F}_{\mathrm{deep}}$ is a filter,
$\mathscr{F}_{\mathrm{pseudo}}$ also forms a filter – in fact, it is the
principal filter generated by $\mathop{\deg_{\mathrm{w}}}(L)$.

######  Theorem VII.2.4.

$\mathscr{F}_{\mathrm{pseudo}}$ is equal to the principal filter generated by
$\mathop{\deg_{\mathrm{w}}}(L)$ in
$\langle\mathcal{E}_{\mathrm{w}},\leq\rangle$.

###### Proof.

Suppose $\mathbf{p}$ is a pseudo-deep degree in $\mathcal{E}_{\mathrm{w}}$.
Let $\mathcal{C}$ be a collection of deep $\Pi^{0}_{1}$ classes such that
$\mathbf{p}=\mathop{\deg_{\mathrm{w}}}(\tbigcup\slimits@{\mathcal{C}})$. Then
$L\supseteq\tbigcup\slimits@{\mathcal{C}}$, so
$\mathop{\deg_{\mathrm{w}}}(L)\leq\mathbf{p}$. This shows that every pseudo-
deep degree in $\mathcal{E}_{\mathrm{w}}$ lies in the filter generated by
$\mathop{\deg_{\mathrm{w}}}(L)$ in
$\langle\mathcal{E}_{\mathrm{w}},\leq\rangle$.

Conversely, suppose
$\mathop{\deg_{\mathrm{w}}}(L)\leq\mathbf{p}\in\mathcal{E}_{\mathrm{w}}$. Let
$P$ be a $\Pi^{0}_{1}$ class for which
$\mathbf{p}=\mathop{\deg_{\mathrm{w}}}(P)$. $(\mathcal{D}_{\mathrm{w}},\leq)$
is completely distributive (Proposition I.4.13(f)), so

$\displaystyle\mathop{\deg_{\mathrm{w}}}(P)$
$\displaystyle=\sup\\{\mathop{\deg_{\mathrm{w}}}(P),\mathop{\deg_{\mathrm{w}}}(L)\\}$
$\displaystyle=\sup\\{\mathop{\deg_{\mathrm{w}}}(P),\inf\\{\mathop{\deg_{\mathrm{w}}}(P_{e})\mid\text{$P_{e}$
is deep}\\}\\}$
$\displaystyle=\inf\\{\sup\\{\mathop{\deg_{\mathrm{w}}}(P),\mathop{\deg_{\mathrm{w}}}(P_{e})\\}\mid\text{$P_{e}$
is deep}\\}$ $\displaystyle=\inf\\{\mathop{\deg_{\mathrm{w}}}(P\times
P_{e})\mid\text{$P_{e}$ is deep}\\}.$

Thus, $\mathbf{p}$ is pseudo-deep. ∎

######  Corollary VII.2.5.

There is no minimal element of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\\{\mathop{\deg_{\mathrm{w}}}(L)\\}$..

###### Proof.

By Theorem VII.2.4, if $\mathbf{p}$ is a pseudo-deep degree distinct from
$\mathop{\deg_{\mathrm{w}}}(L)$ then
$\mathop{\deg_{\mathrm{w}}}(L)\mathrel{<_{\mathrm{w}}}\mathbf{p}$. The Density
Theorem for $\mathcal{E}_{\mathrm{w}}$ [4, Theorem 2] shows that there exists
$\mathbf{q}\in\mathcal{E}_{\mathrm{w}}$ such that
$\mathop{\deg_{\mathrm{w}}}(L)\mathrel{<_{\mathrm{w}}}\mathbf{q}\mathrel{<_{\mathrm{w}}}\mathbf{p}$.
A second application of Theorem VII.2.4 shows $\mathbf{q}$ is a pseudo-deep
degree, and hence $\mathbf{p}$ is not a minimal element of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\\{\mathop{\deg_{\mathrm{w}}}(L)\\}$. ∎

###  VII.3 The Filter of Deep Degrees in $\mathcal{E}_{\mathrm{w}}$ and
Difference Randoms

Proposition VII.2.2 shows that no difference random computes a member of any
$P\subseteq\mathbb{N}^{\mathbb{N}}$ of pseudo-deep degree. However, we can
show that this does not characterize the pseudo-deep degrees.

######  Theorem VII.3.1.

There exists a $\Pi^{0}_{1}$ class $P$ which is not of pseudo-deep degree but
for which no difference random computes an element of $P$.

######  Notation VII.3.2.

Let $\mathscr{F}_{\mathrm{diff}}$ be the collection of all weak degrees
$\mathop{\deg_{\mathrm{w}}}(P)$ in $\mathcal{E}_{\mathrm{w}}$ such that no
difference random computes a member of $P$.

######  Proposition VII.3.3.

$\mathscr{F}_{\mathrm{diff}}$ is a filter.

###### Proof.

Given $\mathbf{p},\mathbf{q}\in\mathcal{E}_{\mathrm{w}}$, let $P$ and $Q$ be
$\Pi^{0}_{1}$ classes such that $\mathop{\deg_{\mathrm{w}}}(P)=\mathbf{p}$ and
$\mathop{\deg_{\mathrm{w}}}(Q)=\mathbf{q}$.

Suppose $\mathbf{p}\in\mathscr{F}_{\mathrm{diff}}$ and
$\mathbf{p}\leq\mathbf{q}\in\mathcal{E}_{\mathrm{w}}$. If
$Y\mathrel{{}_{\mathrm{T}}}X$ for some $Y\in Q$, then
$\mathbf{p}\leq\mathbf{q}$ implies $Z\mathrel{{}_{\mathrm{T}}}Y$ for some
$Z\in P$, from which we find $Z\mathrel{{}_{\mathrm{T}}}X$, a contradiction.
Thus, $\mathbf{q}\in\mathscr{F}_{\mathrm{diff}}$.

Now suppose $\mathbf{p},\mathbf{q}\in\mathscr{F}_{\mathrm{diff}}$.
$\inf\\{\mathbf{p},\mathbf{q}\\}=\mathop{\deg_{\mathrm{w}}}(P\cup Q)$. As no
difference random computes any member of $P$ or $Q$, no difference random
computes any member of $P\cup Q$, i.e.,
$\inf\\{\mathbf{p},\mathbf{q}\\}\in\mathscr{F}_{\mathrm{diff}}$. ∎

We can show that $\mathscr{F}_{\mathrm{pseudo}}\mathrel{\ooalign{\hss\raise
1.29167pt\hbox{$\subset$}\hss\cr\kern
0.86108pt\raise-2.15277pt\hbox{\scalebox{0.7}{$\mathrel{\ooalign{\hss\hbox{\scalebox{1.4}{$-$}}\hss\cr\kern
0.86108pt\raise-0.43057pt\hbox{\rotatebox{45.0}{$-$}}}}$}}}}\mathscr{F}_{\mathrm{diff}}$
by showing that $\mathscr{F}_{\mathrm{diff}}$ is non-principal.

######  Theorem VII.3.4.

$\mathscr{F}_{\mathrm{diff}}$ is non-principal.

To prove Theorem VII.3.4 we make use of the notion of
$\operatorname{KP}$-triviality.

######  Definition VII.3.5 ($\operatorname{KP}$-trivial).

$X\in\\{0,1\\}^{\mathbb{N}}$ is _$\operatorname{KP}$ -trivial_ if there exists
$c\in\mathbb{N}$ such that
$\operatorname{KP}(X{\upharpoonright}\,n)\leq\operatorname{KP}(n)+c$ for all
$n\in\mathbb{N}$.

###### Proof of Theorem VII.3.4..

Suppose $\mathbf{q}\in\mathscr{F}_{\mathrm{diff}}$, and let $Q$ be a
$\Pi^{0}_{1}$ class such that $\mathbf{q}=\mathop{\deg_{\mathrm{w}}}(Q)$. By
[3, Lemma 2], there exist r.e. sets $A,B\subseteq\mathbb{N}$ such that
$0\mathrel{<_{\mathrm{T}}}A,B\mathrel{<_{\mathrm{T}}}0^{\prime}$, $A\cap
B=\emptyset$ and $A\cup B=0^{\prime}$, and for which neither $A$ nor $B$
compute any member of $Q$. Note that $A\oplus
B\mathrel{{}_{\mathrm{T}}}0^{\prime}$.

Lemma II.4.23 implies $\\{A\\}$ and $\\{B\\}$ are $\Pi^{0}_{2}$, so that
$Q\cup\\{A\\}$ and $Q\cup\\{B\\}$ are each $\Pi^{0}_{2}$. Both sets contain a
nonempty $\Pi^{0}_{1}$ class (namely, $Q$), so the  (Embedding Lemma). implies
there are $\Pi^{0}_{1}$ classes $P_{A}$ and $P_{B}$ such that
$P_{A}\mathrel{{}_{\mathrm{w}}}Q\cup\\{A\\}$ and
$P_{B}\mathrel{{}_{\mathrm{w}}}Q\cup\\{B\\}$. Because neither $A$ nor $B$
compute any member of $Q$, we have
$P_{A}\mathrel{{}_{\mathrm{w}}}Q\cup\\{A\\}\mathrel{<_{\mathrm{w}}}Q$ and
$P_{B}\mathrel{{}_{\mathrm{w}}}Q\cup\\{B\\}\mathrel{<_{\mathrm{w}}}Q$.

By [6, Theorem 11.6.2], if $A$ and $B$ are both $\operatorname{KP}$-trivial,
then $A\oplus B\mathrel{{}_{\mathrm{T}}}0^{\prime}$ is
$\operatorname{KP}$-trivial, which is a contradiction. Thus, at least one of
$A$ and $B$ are not $\operatorname{KP}$-trivial. Without loss of generality,
say that $A$ is not $\operatorname{KP}$-trivial, and let $P=P_{A}$.

Suppose $X$ is a difference random. Proposition VII.2.2 shows that $X$
computes no member of $Q$, and if $A\mathrel{{}_{\mathrm{T}}}X$ then [11,
Corollary 3.6] implies $A$ is $\operatorname{KP}$-trivial, contrary to
hypothesis. Thus, $X$ computes no member of $Q\cup\\{A\\}$, and hence computes
no member of $P$, showing
$\mathop{\deg_{\mathrm{w}}}(P)\in\mathscr{F}_{\mathrm{diff}}$. As $\mathbf{q}$
was an arbitrary member of $\mathscr{F}_{\mathrm{diff}}$, it follows that
$\mathscr{F}_{\mathrm{diff}}$ is non-principal. ∎

###### Proof of Theorem VII.3.1..

Proposition VII.3.3 and Theorem VII.3.4 show that
$\mathscr{F}_{\mathrm{diff}}$ is a nonprincipal filter. By Proposition
VII.2.2, $\mathscr{F}_{\mathrm{diff}}\subseteq\mathscr{F}_{\mathrm{pseudo}}$,
but $\mathscr{F}_{\mathrm{pseudo}}$ being principal means this inclusion must
be proper. ∎

All these facts add up to imply Theorem VII.0.1:

###### Proof of Theorem VII.0.1..

Corollary VII.1.3 and Theorem VII.3.4 shows that the outer two are
nonprincipal, while Theorem VII.2.4 shows the middle is. This implies that the
inclusions
$\mathscr{F}_{\mathrm{deep}}\subseteq\mathscr{F}_{\mathrm{pseudo}}\subseteq\mathscr{F}_{\mathrm{diff}}$
must be proper. ∎

###  VII.4 Open questions about the filter of pseudo-deep degrees

Theorem VII.2.4 and Corollary VII.2.5 give important structural information
about the filter of pseudo-deep degrees. However, there remain open questions
about that structure, especially
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$.

######  Question VII.4.1.

What is the cardinality of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$? I.e., how
many pseudo-deep degrees are there which aren’t deep degrees?

Corollary VII.2.5 puts constraints on
$|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|$.

######  Proposition VII.4.2.

$|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|\in\\{1,{}_{0}\\}$.

###### Proof.

Because
$\mathop{\deg_{\mathrm{w}}}(L)\in\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$,
we know
$1\leq|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|$.
$\mathcal{E}_{\mathrm{w}}$ is countable, so
$|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|\leq{}_{0}$.

If
$1<|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|<{}_{0}$,
then
$\mathscr{F}_{\mathrm{pseudo}}\setminus(\mathscr{F}_{\mathrm{deep}}\cup\\{\mathop{\deg_{\mathrm{w}}}(L)\\})$
has a minimal element, and such a minimal element is a minimal element of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\\{\mathop{\deg_{\mathrm{w}}}(L)\\}$
since $\mathscr{F}_{\mathrm{deep}}$ is upward-closed, contradicting Corollary
VII.2.5. ∎

Currently, the only two pseudo-deep degrees known to not be deep are
$\mathop{\deg_{\mathrm{w}}}(L)$ and
$\mathop{\deg_{\mathrm{w}}}(\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}})$,
though they are not known to be distinct.

######  Question VII.4.3.

Are $L$ and $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ weakly equivalent?

Something slightly stronger than asking whether
$L\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ is the
following.

######  Question VII.4.4.

Given a deep $\Pi^{0}_{1}$ class $P$, does there exist a slow-growing order
function $p\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{w}}}P$?

######  Proposition VII.4.5.

  1. (a)

An affirmative answer to Question VII.4.4 gives an affirmative answer to
Question VII.4.3.

  2. (b)

An affirmative answer to Question VII.4.4 gives an affirmative answer to
Question VI.6.3, i.e., for all slow-growing order functions
$p\colon\mathbb{N}\to(1,\infty)$ and $q\colon\mathbb{N}\to(1,\infty)$ there
exists a slow-growing order function $r\colon\mathbb{N}\to(1,\infty)$ such
that
$\mathrm{LU\kern-0.50003ptA}(r)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(p)\cup\mathrm{LU\kern-0.50003ptA}(q)$.

  3. (c)

An answer to Question VII.4.1 of ‘$1$’ gives an affirmative answer to Question
VII.4.3.

An answer to Question VII.4.1 of ‘0’ suggests further structural questions
about antichains in
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$ and
related properties.

######  Question VII.4.6.

  1. (a)

Do there exist weakly incomparable elements of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$?

  2. (b)

Do there exist infinitely many pairwise weakly incomparable elements of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$?

  3. (c)

Is $\mathop{\deg_{\mathrm{w}}}(L)$ meet-irreducible? I.e., are there no
pseudo-deep degrees $\mathbf{p},\mathbf{q}$ such that
$\inf\\{\mathbf{p},\mathbf{q}\\}=\mathop{\deg_{\mathrm{w}}}(L)$?

In contrast, if
$|\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}|={}_{0}$,
then $\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$
contains infinite chains.

One possible approach to answering Question VII.4.1 would be by showing that
$\mathrm{SC}$ is not of deep degree, as it is of pseudo-deep degree and we
know that
$\mathrm{SC}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$
by Theorem VI.4.3.

We observe that the known lattice theoretic properties available are not
enough to determine the structure of
$\mathscr{F}_{\mathrm{pseudo}}\setminus\mathscr{F}_{\mathrm{deep}}$.

######  Remark VII.4.7.

Some lattices $\langle P,\leq\rangle$ and filters
$\mathscr{F}_{1}\mathrel{\ooalign{\hss\raise
1.29167pt\hbox{$\subset$}\hss\cr\kern
0.86108pt\raise-2.15277pt\hbox{\scalebox{0.7}{$\mathrel{\ooalign{\hss\hbox{\scalebox{1.4}{$-$}}\hss\cr\kern
0.86108pt\raise-0.43057pt\hbox{\rotatebox{45.0}{$-$}}}}$}}}}\mathscr{F}_{2}\subseteq
P$ which give some idea of how the boundary between
$\mathscr{F}_{\mathrm{pseudo}}$ and $\mathscr{F}_{\mathrm{deep}}$ might look
include the following:

  * •

Consider the lattice $\langle
P,\leq\rangle\mathrel{{\vdotdot}{\equal}}\langle\\{S\subseteq[0,1]\mid|S|\leq{}_{0}\\}\cup\\{[0,1]\\},\supseteq\rangle$
and the filters
$\mathscr{F}_{1}\mathrel{{\vdotdot}{\equal}}\\{S\subseteq[0,1]\mid|S|<{}_{0}\\}$
and $\mathscr{F}_{2}=P$. In this case,
$|\mathscr{F}_{2}\setminus\mathscr{F}_{1}|={}_{0}$ and the minimum of
$\mathscr{F}_{2}$, $[0,1]$, is meet-irreducible.

  * •

Consider the lattice $\langle
P,\leq\rangle\mathrel{{\vdotdot}{\equal}}\langle\\{S\subseteq\mathbb{N}\mid|S|<{}_{0}\vee|\mathbb{N}\setminus
S|<{}_{0}\\},\supseteq\rangle$ and the filters
$\mathscr{F}_{1}\mathrel{{\vdotdot}{\equal}}\\{S\subseteq\mathbb{N}\mid|S|<{}_{0}\\}$
and $\mathscr{F}_{2}=P$. In this case,
$|\mathscr{F}_{2}\setminus\mathscr{F}_{1}|={}_{0}$ and the minimum of
$\mathscr{F}_{2}$, $\mathbb{N}$, is not meet-irreducible.

## REFERENCES

  * [1] Laurent Bienvenu and Ludovic Patey, _Diagonally non-computable functions and fireworks_ , 2016.
  * [2] Laurent Bienvenu and Christopher P. Porter, _Deep $\Pi_{1}^{0}$ classes_, The Bulletin of Symbolic Logic 22 (2016), no. 2, 249–286.
  * [3] Stephen Binns, _A splitting theorem for the Medvedev and Muchnik lattices_ , Mathematical Logic Quarterly 49 (2003), no. 4, 327–335.
  * [4] Stephen Binns, Richard A. Shore, and Stephen G. Simpson, _Mass problems and density_ , Journal of Mathematical Logic 16 (2016), no. 02, 1650006.1 – 1650006.10, 10 pages.
  * [5] Cristian S. Calude, Ludwig Staiger, and Sebastiaan A. Terwijn, _On partial randomness_ , Annals of Pure and Applied Logic 138 (2006), no. 1, 20–30.
  * [6] Rodney G. Downey and Denis R. Hirschfeldt, _Algorithmic Randomness and Complexity_ , Theory and Applications of Computability, Springer-Verlag, New York, 2010, xxviii + 855 pages.
  * [7] Bruno Durand, Leonid Levin, and Alexander Shen, _Complex tilings_ , Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’01, Association for Computing Machinery, 2001, pp. 732–739.
  * [8] Bruno Durand, Leonid A. Levin, and Alexander Shen, _Complex tilings_ , J. Symbolic Logic 73 (2008), no. 2, 593–613.
  * [9] Noam Greenberg and Joseph S. Miller, _Diagonally non-recursive functions and effective Hausdorff dimension_ , Bulletin of the London Mathematical Society 43 (2011), no. 4, 636–654.
  * [10] Kojiro Higuchi, WM. Phillip Hudelson, Stephen G. Simpson, and Keita Yokoyama, _Propagation of partial randomness_ , Annals of Pure and Applied Logic 165 (2014), no. 2, 742–758.
  * [11] Denis R. Hirschfeldt, André Nies, and Frank Stephan, _Using random sets as oracles_ , Journal of the London Mathematical Society 75 (2007), no. 3, 610–622.
  * [12] W. M. Phillip Hudelson, _Mass problems and initial segment complexity_ , Journal of Symbolic Logic 79 (2014), no. 1, 20–44.
  * [13] WM. Phillip Hudelson, _Partial randomness and Kolmogorov complexity_ , Ph.D. thesis, 2013, URL: https://etda.libraries.psu.edu/files/final_submissions/8355.
  * [14] Carl G. Jockusch and Robert I. Soare, _$\Pi^{0}_{1}$ classes and degrees of theories_, Transactions of the American Mathematical Society 173 (1972), 35–56.
  * [15] Mushfeq Khan, _Shift-complex sequences_ , Bull. Symbolic Logic 19 (2013), no. 2, 199–215.
  * [16] Mushfeq Khan and Joseph S. Miller, _Forcing with bushy trees_ , The Bulletin of Symbolic Logic 23 (2017), no. 2, 160–180.
  * [17] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan, _Kolmogorov complexity and the recursion theorem_ , STACS 2006 (Berlin, Heidelberg) (Bruno Durand and Wolfgang Thomas, eds.), Springer Berlin Heidelberg, 2006, pp. 149–161.
  * [18] Joseph S. Miller, _Two notes on subshifts_ , Proceedings of the American Mathematical Society 140 (2012), no. 5, 1617–1622.
  * [19] , _Assorted results in and about effective randomness_ , unpublished manuscript, 27 pages, 2020.
  * [20] Hartley Rogers, _Godel numberings of partial recursive functions_ , J. Symbolic Logic 23 (1958), no. 3, 331–341.
  * [21] Hartley Rogers, Jr, _Theory of Recursive Functions and Effective Computability_ , McGraw-Hill Series in Higher Mathematics, McGraw-Hill, 1967, xix + 482 pages.
  * [22] A. Yu. Rumyantsev and M. A. Ushakov, _Forbidden substrings, kolmogorov complexity and almost periodic sequences_ , STACS 2006 (Berlin, Heidelberg) (Bruno Durand and Wolfgang Thomas, eds.), Springer Berlin Heidelberg, 2006, pp. 396–407.
  * [23] Andrey Yu. Rumyantsev, _Everywhere complex sequences and the probabilistic method_ , 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany (Thomas Schwentick and Christoph Dürr, eds.), LIPIcs, vol. 9, Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2011, pp. 464–471.
  * [24] Stephen G. Simpson, _Mass problems and randomness_ , Bulletin of Symbolic Logic 11 (2005), no. 1, 1–27.
  * [25] , _An extension of the recursively enumerable Turing degrees_ , Journal of the London Mathematical Society 75 (2007), no. 2, 287–297.
  * [26] Stephen G. Simpson, _Computability, Unsolvability, Randomness_ , 2009, URL: http://www.personal.psu.edu/t20/notes/cur.pdf. Last visited on 2021/02/23.
  * [27] Stephen G. Simpson, _Degrees of Unsolvability. Lectures Notes for “Mass Problems”, Spring 2009 at the Pennsylvania State University_ , 2009, URL: http://www.personal.psu.edu/t20/notes/dou.pdf. Last visited on 2019/04/19.
  * [28] Stephen G. Simpson, _Foundations of Mathematics. Lecture Notes for “Foundations of Mathematics i”, Fall 2009 at the Pennsylvania State University_ , 2009, URL: http://www.personal.psu.edu/t20/notes/fom.pdf.
  * [29] Stephen G. Simpson, _Turing degrees and Muchnik degrees of recursively bounded DNR functions_ , Computability and Complexity, Springer, 2017, pp. 660–668.
  * [30] Robert I. Soare, _Recursively Enumerable Sets and Degrees_ , Perspective in Mathematical Logic, Springer-Verlag, Berlin Heidelberg, 1987, xviii + 427 pages.
  * [31] , _Turing Computability: Theory and Applications_ , Theory and Applications of Computability, Springer-Verlag, Berlin Heidelberg, 2016, xxxvi + 263 pages.
  * [32] A. K. Zvonkin and L. A. Levin, _The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms_ , Russian Mathematical Surveys 25 (1970), no. 6, 83–124.