Complexity and Avoidance

By
Hayden Robert Jananthan

Dissertation

Submitted to the Faculty of the

Graduate School of Vanderbilt University

in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY

in

Mathematics

June 30th, 2021

Nashville, Tennessee

Approved,

Douglas H. Fisher, Ph.D.

Alexander Y. Olshanskii, Ph.D.

Denis V. Osin, Ph.D.

Stephen G. Simpson, Ph.D.

Constantine Tsinakis, Ph.D.

Copyright © 2021 by Hayden Robert Jananthan

All Rights Reserved

Dedicated to Lekha

## ACKNOWLEDGEMENTS

My utmost thanks is to my advisor, Steve Simpson, who has guided me through
this nearly five-year journey, starting all the way back to the our first
independent studies course in my second semester. Steve’s support, knowledge,
and direction has been invaluable in my growth as a mathematician, and I know
I’ve been lucky to have him as my advisor.

I would also like to thank my fellow graduate students and my instructors
during my time here at Vanderbilt. Overall, the Vanderbilt Mathematics
Department has proven to be a welcoming and tight-knit community. Between
breath-taking hikes in the mountains, costume parties and soirees, and the
simple satisfaction of drinks at KayBob’s or food at McDougal’s (among many
other things), I know that I’ve made wonderful friends and wonderful memories
here. Special thanks should be given to my roommate, Dumindu De Silva, who has
never complained about me regularly mulling about our apartment at absurd
hours of the night and morning.

Thanks is due to some of my colleagues, mentors, and instructors at MIT. My
first forays into research, publishing, and supervising are thanks to Dr.
Jeremy Kepner and Dr. Vijay Gadepally, and I continue to learn countless
things from them and the Lincoln Laboratory Supercomputing Center as a whole.
I must also thank Prof. Henry Cohn, who’s brilliant instruction of 18.510
secured my interest in logic early in my academic journey, and Prof. Michael
Sipser, who gave me my first taste of computability theory in 18.404.

I would like to thank my family, all of whom have been supportive throughout
the process and have put up with many a mathematical jargon-filled phone call.
Finally, I want to give my deepest thanks to my wife Lekha, a beautiful person
inside and out who has been a rock that has anchored me over these years. I’m
not sure where I would be without her support, and I look forward to a bright
future.

###### TABLE OF CONTENTS

  1. ACKNOWLEDGEMENTS
  2. I Introduction
    1. I.1 Summary of Chapters
      1. I.2 Basic Conventions and Notation
      2. I.3 Computability - Definitions, Notation, and Conventions
        1. I.3.1 (Partial) Recursive Functions and Sets
        2. I.3.2 Enumerations of the Partial Recursive Functions
        3. I.3.3 Partial Recursive Functionals
        4. I.3.4 The Arithmetical Hierarchy
        5. I.3.5 Recursive Reals and Real-Valued Functions
      3. I.4 Reducibility Notions
        1. I.4.1 Turing Reducibility
        2. I.4.2 Mass Problems and Weak, Strong Reducibility
        3. I.4.3 $\mathcal{E}_{\mathrm{w}}$ and the Embedding Lemma
      4. II Complexity, Avoidance, and Depth
        1. II.1 Algorithmic Randomness and Complexity
          1. II.1.1 Martin-Löf Randomness
          2. II.1.2 Partial Randomness
          3. II.1.3 Randomness and Complexity as Mass Problems
          4. II.1.4 Properties of Prefix-Free Complexity
        2. II.2 $\mathrm{DNR}$ and Avoidance
          1. II.2.1 Linearly Universal Avoidance
          2. II.2.2 Properties of Linearly Universal Partial Recursive Functions
        3. II.3 Fast & Slow-Growing Order Functions
          1. II.3.1 Bounding Sequences of Fast & Slow-Growing Order Functions
          2. II.3.2 More about Recursive Sums
          3. II.3.3 The Fast and Slow-Growing $\mathrm{LU\kern-0.50003ptA}$ Hierarchies
        4. II.4 Depth
          1. II.4.1 Depth and Difference Randoms
          2. II.4.2 Depth and Strong Reducibility
          3. II.4.3 Depth and Weak Reducibility
          4. II.4.4 Depth for non-r.b. $\Pi^{0}_{1}$ Sets
      5. III Complexity and Fast-Growing Avoidance
        1. III.1 Extracting Fast-Growing Avoidance from Complexity
        2. III.2 Extracting Complexity from Fast-Growing Avoidance
        3. III.3 Finding Complexity Above Fast-Growing Avoidance
      6. IV Complexity and Slow-Growing Avoidance
        1. IV.1 Partial Randomness in $h^{\mathbb{N}}$
          1. IV.1.1 $f$-randomness and $f$-complexity
          2. IV.1.2 Strong $f$-Randomness
          3. IV.1.3 Relationships between randomness notions
        2. IV.2 Randomness in $h^{\mathbb{N}}$ versus $\\{0,1\\}^{\mathbb{N}}$
          1. IV.2.1 Randomness in $[0,1]$ versus $\\{0,1\\}^{\mathbb{N}}$
          2. IV.2.2 Randomness in $h^{\mathbb{N}}$ versus $[0,1]$
          3. IV.2.3 Improving Greenberg & Miller’s Conclusion
        3. IV.3 Quantifying the Reduction of Avoidance to Complexity – Preliminary Case
        4. IV.4 Quantifying the Reduction of Avoidance to Complexity – General Case
        5. IV.5 Open Questions
      7. V Generalized Shift Complexity
        1. V.1 $\delta$-Shift Complexity as a Mass Problem
          1. V.1.1 Shift Complexity and Depth
          2. V.1.2 Shift Complexity and Avoidance
        2. V.2 Generalized Shift Complexity
        3. V.3 Generalized Shift Complexity and Depth
          1. V.3.1 Relating Generalized Shift Complexity and Complexity
          2. V.3.2 Extracting Generalized Shift Complexity from Sublinear Complexity
          3. V.3.3 Strong Shift Complexity and Depth
        4. V.4 Open Questions
      8. VI Avoidance – Slow-Growing versus Fast-Growing
        1. VI.1 Bushy Trees
        2. VI.2 Avoidance of Individual Universal Partial Recursive Functions
        3. VI.3 Avoidance of Well-Behaved Families of Universal Partial Recursive Functions
        4. VI.4 Implications for $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$
        5. VI.5 Replacing Slow-Growing with Depth
        6. VI.6 Open Problems
      9. VII Structure of the Deep Region of $\mathcal{E}_{\mathrm{w}}$
        1. VII.1 The infimum of all deep degrees
        2. VII.2 The Filter of Pseudo-Deep Degrees
        3. VII.3 The Filter of Deep Degrees in $\mathcal{E}_{\mathrm{w}}$ and Difference Randoms
        4. VII.4 Open questions about the filter of pseudo-deep degrees

###### LIST OF FIGURES

  1. I.2 Summary of specific examples of reductions between the hierarchies of interest. Within each row, the conditions listed in the right-most column are assumed for the given reduction.
  2. I.3 Collected result and section references related to reductions of the form $P\mathrel{{}_{\mathrm{w}}}Q$ or $P\mathrel{\mathrel{{}_{\mathrm{w}}}}Q$, where $P$ is a member of the hierarchy corresponding to the row and $Q$ is a member of the hierarchy corresponding to the column. The $\mathrm{COMPLEX}$ row also contains references related to (non)negligibility and depth.
  3. I.4 Collected open question references related to reductions of the form $P\mathrel{{}_{\mathrm{w}}}Q$ or $P\mathrel{\mathrel{{}_{\mathrm{w}}}}Q$, where $P$ is a member of the hierarchy corresponding to the row and $Q$ is a member of the hierarchy corresponding to the column. The $\mathrm{COMPLEX}$ row also contains references related to (non)negligibility and depth.
  4. I.5 Visual representation of $\mathcal{E}_{\mathrm{w}}$ and the relationships between the hierarchies of interest within. $p$ denotes a slow-growing order function, $q$ denotes a slow-growing order function, $f$ denotes a sub-identical order function, $g$ denotes an order function satisfying $\tsum\slimits@_{m=0}{g(2^{m})/2^{m}}<\infty$, and $\delta$ denotes a rational number in $(0,1)$.

##  Chapter I Introduction

A subset $P$ of $\mathbb{N}^{\mathbb{N}}$ may be considered a ‘problem’ whose
‘solutions’ are its elements, as in the problems “Find a completion of
$\mathsf{PA}$” or “Find a $1$-random infinite binary sequence”, corresponding
to the subsets $\mathrm{CPA}$ and $\mathsf{MLR}$, respectively. In this
context, we call $P$ a _mass problem_. To compare the ‘degree of
unsolvability’ of two mass problems $P$ and $Q$, one approach is to use weak
reducibility, where $P\mathrel{{}_{\mathrm{w}}}Q$ if and only if every member
of $Q$ computes a member of $P$.

Two well-studied hierarchies of mass problems are the complexity and
diagonally non-recursive hierarchies. The former consists of the sets

$\mathrm{COMPLEX}(f)\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$\operatorname{KP}(X{\upharpoonright}\,n)\geq
f(n)-O(1)$ for all $n$}\\}$

where $f\colon\mathbb{N}\to[0,\infty)$ is an unbounded, nondecreasing,
computable function (an _order function_) and $\operatorname{KP}$ is prefix-
free Kolmogorov complexity. In other words, $\mathrm{COMPLEX}(f)$ consists of
all infinite binary sequences whose first $n$ bits cannot be described with
less than $f(n)$ bits of information, up to addition of a constant. The latter
hierarchy consists of the sets

$\mathrm{DNR}(p)\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid\text{$X(n)\nsimeq\varphi_{n}(n)$
and $X(n)<p(n)$ for all $n$}\\}$

where $p\colon\mathbb{N}\to(1,\infty)$ is a nondecreasing, computable function
and $\varphi_{n}$ is the $n$-th $1$-place partial recursive function. In other
words, $\mathrm{DNR}(p)$ consists of all $p$-bounded infinite sequences which
avoid the diagonal of a fixed enumeration of the $1$-place partial recursive
functions.

Although the two hierarchies are quite different in presentation, the
connections between them have been widely studied. Among them is a result of
Kjos-Hanssen, Merkle, & Stephan [17, Theorem 2.3] which shows that the
complexity and diagonally non-recursive hierarchies are tightly coupled when
going downward:

######  Theorem.

[17, Theorem 2.3] Suppose $X\in\\{0,1\\}^{\mathbb{N}}$. Then the following are
equivalent.

  1. (i)

$X\in\mathrm{COMPLEX}(f)$ for some order function
$f\colon\mathbb{N}\to{[0,\infty)}$.

  2. (ii)

There exists an order function $p\colon\mathbb{N}\to(1,\infty)$ and a
$Y\in\mathrm{DNR}(p)$ such that $Y$ is computable from $X$.

Two other connections were proven by Greenberg & Miller [9], relating the
diagonally non-recursive hierarchy to the upper levels of the complexity
hierarchy. The former says that regardless of how slow-growing an order
function $p$ is, there is an $X\in\mathrm{DNR}(p)$ which cannot compute a
maximally complex infinite binary sequence (an element of
$\mathrm{COMPLEX}(\operatorname{id}_{\mathbb{N}})$), while the latter gives an
upshot that if $p$ is sufficiently slow-growing then any $X\in\mathrm{DNR}(p)$
computes highly complex infinite binary sequences.

######  Theorem.

[9, Theorem 5.11] If $p\colon\mathbb{N}\to(1,\infty)$ is an order function,
then there exists $X\in\mathrm{DNR}(p)$ such that $X$ computes no member of
$\mathrm{COMPLEX}(\lambda n.n)$.

######  Theorem.

[9, Theorem 4.9] For all sufficiently slow-growing order functions
$p\colon\mathbb{N}\to(1,\infty)$, every $X\in\mathrm{DNR}(p)$ computes a
member of $\tbigcap\slimits@_{0\leq\delta<1}{\mathrm{COMPLEX}(\lambda n.\delta
n)}$.

In [29], Simpson introduced a variation of $\mathrm{DNR}$,
$\mathrm{LU\kern-0.50003ptA}$ (Linearly Universal Avoidance)111The notation
used by Simpson in [29] was $\mathrm{LDNR}$, standing for Linearly Diagonally
Non-Recursive., to remove its dependence on any specific choice of enumeration
of the partial recursive functions as well as to more closely tie the growth
rate of $p$ to the degree of unsolvability of the class
$\mathrm{LU\kern-0.50003ptA}(p)$. For any order function $p$ there are order
functions $p^{+}$ and $p^{-}$ such that any $X\in\mathrm{DNR}(p^{+})$ computes
a member of $\mathrm{LU\kern-0.50003ptA}(p)$ and any
$Y\in\mathrm{LU\kern-0.50003ptA}(p)$ computes a member of
$\mathrm{DNR}(p^{-})$, so all of the aforementioned results linking the
complexity and diagonally non-recursive hierarchies translate to the
$\mathrm{LU\kern-0.50003ptA}$ hierarchy.

An observation made by Bienvenu & Porter [2], Greenberg, Miller [19], and
Slaman is that the behavior of $\mathrm{DNR}(p)$ (for specific types of
enumerations of the partial recursive functions) changes significantly
depending on whether the series $\tsum\slimits@_{n=0}{p(n)^{-1}}$ converges
(in which case $p$ is called _fast-growing_) or diverges (in which case $p$ is
called _slow-growing_), and this observation applies to
$\mathrm{LU\kern-0.50003ptA}$ as well [29, Theorem 5.4]. Thus, we may consider
the $\mathrm{LU\kern-0.50003ptA}$ hierarchy as being made up of two sub-
hierarchies, the _fast-growing $\mathrm{LU\kern-0.50003ptA}$ hierarchy_
(consisting of $\mathrm{LU\kern-0.50003ptA}(p)$ for fast-growing $p$) and the
_slow-growing $\mathrm{LU\kern-0.50003ptA}$ hierarchy_ (consisting of
$\mathrm{LU\kern-0.50003ptA}(p)$ for slow-growing $p$).

Within $\mathcal{E}_{\mathrm{w}}$ (where our degrees of interest lie) there is
a subregion in its upper reaches consisting of so-called ‘deep degrees’. The
slow-growing $\mathrm{LU\kern-0.50003ptA}$ hierarchy lies in this subregion,
while both the fast-growing $\mathrm{LU\kern-0.50003ptA}$ and complexity
hierarchies lies in its complement. The notion of ‘shift complexity’ provides
a randomness notion lying in that deep region, providing another way to study
the connections between the slow-growing $\mathrm{LU\kern-0.50003ptA}$
hierarchy and randomness/complexity notions.

Our goal is to explore the relationships between the complexity, fast-growing
$\mathrm{LU\kern-0.50003ptA}$, shift complexity, and slow-growing
$\mathrm{LU\kern-0.50003ptA}$ hierarchies, expanding existing relationships
and providing explicit bounds on the growth rates of the corresponding order
functions.

###  I.1 Summary of Chapters

Each chapter is summarized below. Additionally, Figure Theorem VII.0.1
summarizes the main general reductions proven, Figure I.2 summarizes specific
examples of reductions, and Figures I.3 and I.4 collect references to the
results, sections, and questions pertaining to each of the explored
relationships between the hierarchies of interest. Figure I.5 gives a visual
representation of $\mathcal{E}_{\mathrm{w}}$ and how the hierarchies of
interest sit within it.

##### Chapter I

The remainder of this chapter covers notation, conventions, and terminology.
Section I.2 covers basic notions, such as notation and terminology for number
systems, set theoretic functions & relations, strings over a set, the Cantor &
Baire spaces, and various encoding functions. Section I.3 gives a brief
overview of the relevant notation and terminology from computability theory.
Finally, Section I.4 briefly reviews the Turing, weak, & strong reducibility
notions and the classes of mass problems we will be principally interested in.

##### Chapter II

This chapter serves to introduce many of the main notions discussed within the
remainder of the document. We start by giving a brief overview of partial
randomness, reviewing the notation, terminology, and some basic results.
Following that, we discuss $\mathrm{DNR}$ and its dependence on a choice of an
enumeration of the partial recursive functions, using its definition to
motivate the definition of the class $\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$
for a recursive $p\colon\mathbb{N}\to(1,\infty)$ and a partial recursive
$\psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$. After defining the family of linearly universal
partial recursive functions, we define $\mathrm{LU\kern-0.50003ptA}(p)$,
covering some of the basic reducibility results between those classes. The
fast-growing, slow-growing dichotomy is examined, where we state and prove
several technical results used later. Finally, we define depth and discuss the
weak degrees of deep $\Pi^{0}_{1}$ classes, the basic structure of the region
of deep degrees in $\mathcal{E}_{\mathrm{w}}$ and its relation to the fast-
growing $\mathrm{LU\kern-0.50003ptA}$ and slow-growing
$\mathrm{LU\kern-0.50003ptA}$ hierarchies.

##### Chapter III

This chapter is centered around the relationships between the complexity and
fast-growing $\mathrm{LU\kern-0.50003ptA}$ hierarchies. One way in which we do
this is by strengthening [17, Theorem 2.3], addressing the problems “given
$f$, find $q$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(f)$”
and “given $p$, find $g$ such that
$\mathrm{COMPLEX}(g)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(p)$”
and giving explicit bounds for each. In particular, one of our main theorems
is the following.

######  Theorem III.0.5.

To each sub-identical order function $f\colon\mathbb{N}\to{[0,\infty)}$ there
is a fast-growing order function $q\colon\mathbb{N}\to(1,\infty)$ such that
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(f)$,
and to each fast-growing order function $p\colon\mathbb{N}\to(1,\infty)$ there
is a sub-identical order function $g\colon\mathbb{N}\to{[0,\infty)}$ such that
$\mathrm{COMPLEX}(g)\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(p)$.

We also address the ‘upward’ problem “given $p$ fast-growing, find sub-
identical $g$ such that
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{w}}}\mathrm{COMPLEX}(g)$”,
giving a partial answer.

######  Theorem III.3.3.

If $p\colon\mathbb{N}\to(1,\infty)$ is a fast-growing order function such that
$\tsum\slimits@_{n=0}{p(n)^{-1}}$ is a recursive real, then there exists a
convex sub-identical order function $g$ such that
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(g)\neq\mathsf{MLR}$.

##### Chapter IV

In this chapter we address the problem “given $f$, find $q$ such that
$\mathrm{COMPLEX}(f)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$”,
giving a partial answer and providing explicit bounds for those cases. Our
main results are the following.

######  Theorem IV.4.10.

Given an order function $\Delta\colon\mathbb{N}\to[0,\infty)$ such that
$\lim_{n\to\infty}{\Delta(n)/\sqrt{n}}=0$ and any rational
$\varepsilon\in(0,1)$,

$\mathrm{COMPLEX}\bigl{(}\lambda
n.n-\sqrt{n}\cdot\Delta(n)\bigr{)}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda
n.\exp_{2}\bigl{(}(1-\varepsilon)\Delta(\log_{2}\log_{2}n)\bigr{)}\bigr{)}.$

More generally, $\mathrm{COMPLEX}(\lambda
n.n-\sqrt{n}\cdot\Delta(n))\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$
for any order function $q$ satisfying

$q\left(\exp_{2}((1-\varepsilon)^{-1}\cdot[(n+1)^{2}-(n+1)\cdot\Delta((n+1)^{2})]\cdot\ell(n))\right)\leq\ell(n)$

for almost all $n\in\mathbb{N}$, where
$\ell(n)=\exp_{2}\left((1-\varepsilon)[(n+1)\cdot\Delta((n+1)^{2})-n\cdot\Delta(n^{2})]\right)$.

##### Chapter V

In this chapter we examine classes of ‘shift complex’ sequences – in which the
prefix-free complexity of all segments of a sequence $X$ are quantified rather
than only the initial segments – with respect to (non)negligibility and depth,
as well as relationships with the complexity and $\mathrm{LU\kern-0.50003ptA}$
hierarchies. Our main results are the following.

######  Theorem V.1.8.

(Corollary of Theorem V.1.7) Fix a rational $\varepsilon>0$. For all rational
$\delta\in(0,1)$ we have

$\mathrm{SC}(\delta)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda
n.(\log_{2}n)^{1-\varepsilon}\bigr{)}.$

######  Theorem V.3.12.

Suppose $f$ is a sub-identical order function such that
$\tsum\slimits@_{m=0}{f(2^{m})/2^{m}}$ converges to a recursive real. Then
there is an order function $g$ such that
$\mathrm{SC}(f)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(g)$ and for which
$\lim_{n\to\infty}{g(n)/n}=0$.

##### Chapter VI

This chapter focuses on the relationships between the fast and slow-growing
$\mathrm{LU\kern-0.50003ptA}$ subhierarchies and their structures, with
applications to the depth properties of the boundaries of the slow-growing
$\mathrm{LU\kern-0.50003ptA}$ hierarchy and relationships with the shift
complexity hierarchy. Our main results are the following.

######  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.

######  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}}$.

##### Chapter VII

Using results of the previous chapters, we further explore the structure of
the region of deep degrees in $\mathcal{E}_{\mathrm{w}}$ and a larger region
consisting of ‘pseudo-deep’ degrees in $\mathcal{E}_{\mathrm{w}}$. Our main
result is the following.

######  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}}}X))\\}$

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}}$.

Figure I.1: Summary of general reductions between the hierarchies of interest.
Within each row, the conditions listed in the right-most column are assumed
for the given reduction. In addition, all functions are assumed to be order
functions, $f$ sub-identical, and $p$ fast-growing.
$\mathbb{R}_{\mathrm{rec}}$ is the set of recursive reals.

III.1.2 |  $\displaystyle\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.\exp_{2}((f^{\mathrm{inv}}\circ h)(n)+1)\bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(f)$ | $\scalebox{0.8}{$\displaystyle\tsum\slimits@_{n=0}$}{\frac{1}{2^{h(n)}}}\in\mathbb{R}_{\mathrm{rec}}$
---|---|---
III.2.1 |  $\displaystyle\mathrm{COMPLEX}\Bigl{(}\bigl{(}\lambda n.\raisebox{1.00006pt}{\scalebox{0.9}{$\displaystyle\tsum\slimits@$}}_{i<r(n)}{\lfloor\log_{2}p(i)\rfloor}\bigr{)}^{\mathrm{inv}}\Bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(p)$ |  $\displaystyle\lim_{n\to\infty}\textstyle{\frac{r(n)}{2^{n}}}=\infty$
III.3.4 |  $\displaystyle\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}\bigl{(}\lambda n.\log_{2}\tilde{p}\bigl{(}p^{\mathrm{inv}}(2^{n+1})-1\bigr{)}\bigr{)}$ |  $\scalebox{0.8}{$\displaystyle\tsum\slimits@_{n=0}$}{\frac{1}{\tilde{p}(n)}}\in\mathbb{R}_{\mathrm{rec}}$, $\displaystyle\lim_{n\to\infty}\textstyle{\frac{p(n)}{\tilde{p}(n+3)}}=\infty$
IV.4.10 |  $\displaystyle\mathrm{COMPLEX}\bigl{(}\lambda n.n-\sqrt{n}\cdot\Delta(n)\bigr{)}\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.\exp_{2}\bigl{(}(1-\varepsilon)\Delta(\log_{2}\log_{2}n)\bigr{)}\bigr{)}$ |  $0<\varepsilon<1$, $\displaystyle\lim_{n\to\infty}\textstyle{\frac{\Delta(n)}{\sqrt{n}}}=0$
V.1.8 |  $\displaystyle\mathrm{SC}(f)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.(\log_{2}n)^{1-\varepsilon}\bigr{)}$ |  $\\!\\!\\!\limsup_{n}{\frac{f(n)}{n}}<1$, $0<\varepsilon<1$
V.3.9 |  $\displaystyle\mathrm{SC}(f)\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\delta)$ |  $\scalebox{0.8}{$\displaystyle\tsum\slimits@_{m=0}$}{\frac{f(2^{m})}{2^{m}}}<\infty$, $0<\delta\leq 1$
Figure I.2: Summary of specific examples of reductions between the hierarchies of interest. Within each row, the conditions listed in the right-most column are assumed for the given reduction. III.1.6 |  $\displaystyle\mathrm{LU\kern-0.50003ptA}\Bigl{(}\lambda n.4\sqrt[\delta]{n\cdot\log_{2}n\mathbin{\@cdots}\log_{2}^{k-1}n\cdot(\log_{2}^{k}n)^{(1+\varepsilon)}}\Bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\delta)$ |  $0<\delta\leq 1$, $k\in\mathbb{N}$, $0<\varepsilon$
---|---|---
III.1.7 |  $\displaystyle\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.4\exp_{2}\bigl{(}\sqrt[\alpha]{(1+\varepsilon)\log_{2}n}\bigr{)}\bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda n.n^{\alpha})$ |  $0<\alpha\leq 1$, $0<\varepsilon$
III.1.8 |  $\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.4\exp_{2}(n^{(1+\varepsilon)/\beta})\bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda n.\beta\log_{2}n)$ |  $0<\beta$, $0<\varepsilon$
III.2.2 |  $\mathrm{COMPLEX}(\lambda n.(1/2-\varepsilon)\log_{2}n)\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(\lambda n.2^{n})$ |  $0<\varepsilon<1/2$
IV.3.1 |  $\displaystyle\mathrm{COMPLEX}(\lambda n.n-(1+\varepsilon)\sqrt{n}\log_{2}n)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}\bigl{(}\lambda n.(\log_{2}n)^{1/2-\varepsilon}\bigl{)}$ |  $0<\varepsilon<1/2$
V.1.8 |  $\displaystyle\mathrm{SC}(\delta)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(\lambda n.\bigl{(}\log_{2}n)^{1-\varepsilon}\bigr{)}$ |  $0<\delta<1$, $0<\varepsilon<1$
V.3.10 |  $\displaystyle\mathrm{SC}(\lambda n.n^{\alpha})\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}(\lambda n.n^{\alpha+\varepsilon})$ |  $0<\alpha<1$, $0<\varepsilon\leq 1-\alpha$
V.3.11 |  $\displaystyle\mathrm{SC}\bigl{(}\lambda n.n/(\log_{2}n)^{\alpha+1+\varepsilon}\bigr{)}\mathrel{{}_{\mathrm{s}}}\mathrm{COMPLEX}\bigl{(}\lambda n.n/(\log_{2}n)^{\alpha}\bigr{)}$ |  $0<\alpha$, $0<\varepsilon$
Figure I.3: Collected result and section references related to reductions of the form $P\mathrel{{}_{\mathrm{w}}}Q$ or $P\mathrel{\mathrel{{}_{\mathrm{w}}}}Q$, where $P$ is a member of the hierarchy corresponding to the row and $Q$ is a member of the hierarchy corresponding to the column. The $\mathrm{COMPLEX}$ row also contains references related to (non)negligibility and depth. |  $\mathrm{COMPLEX}$ |  $\mathrm{LU\kern-0.50003ptA}_{\mathrm{fast}}$ |  $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ |  $\mathrm{SC}$
---|---|---|---|---
$\mathrm{COMPLEX}$ |  |  II.4.12(a), III.0.2, III.0.5, §III.2 |  II.4.12(b), II.4.21, IV.2.21, §IV.3, §IV.4, VI.4.1 |  §V.1.1, §V.3.3
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{fast}}$ |  III.0.2, III.0.5, §III.1, §III.3 |  II.2.16 |  II.2.16, §II.3.3, VI.2.1 |
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ |  |  II.3.14 |  II.2.16, II.3.14, VI.2.1, VI.4.2 |
$\mathrm{SC}$ |  V.3.1, V.3.2 |  |  VI.4.3, VI.4.4 |

Figure I.4: Collected open question references related to reductions of the form $P\mathrel{{}_{\mathrm{w}}}Q$ or $P\mathrel{\mathrel{{}_{\mathrm{w}}}}Q$, where $P$ is a member of the hierarchy corresponding to the row and $Q$ is a member of the hierarchy corresponding to the column. The $\mathrm{COMPLEX}$ row also contains references related to (non)negligibility and depth. |  $\mathrm{COMPLEX}$ |  $\mathrm{LU\kern-0.50003ptA}_{\mathrm{fast}}$ |  $\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ |  $\mathrm{SC}$
---|---|---|---|---
$\mathrm{COMPLEX}$ |  |  IV.5.3, IV.5.4
|  IV.5.1, IV.5.2 |  V.4.5, V.4.9
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{fast}}$ |  III.3.12 |
|  VI.6.1 |
$\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}$ |  |  |  VI.6.1, VI.6.2, VI.6.3 |  V.4.10
$\mathrm{SC}$ |  V.4.11 |  |  V.1.2, VI.6.6 |  V.4.1, V.4.2, V.4.3, V.4.4, V.4.6
Figure I.5: Visual representation of $\mathcal{E}_{\mathrm{w}}$ and the
relationships between the hierarchies of interest within. $p$ denotes a slow-
growing order function, $q$ denotes a slow-growing order function, $f$ denotes
a sub-identical order function, $g$ denotes an order function satisfying
$\tsum\slimits@_{m=0}{g(2^{m})/2^{m}}<\infty$, and $\delta$ denotes a rational
number in $(0,1)$.

$\mathcal{D}_{\mathrm{w}}$$\mathcal{E}_{\mathrm{w}}$$\mathbf{1}\mbox{=}\sup\mathcal{E}_{\mathrm{w}}$$\mathbf{d}_{q}$$\mathbf{s}_{\delta}$$\mathbf{d}_{\mathrm{slow}}$$\mathop{\deg_{\mathrm{w}}}(L)$$\mathbf{r}_{1}$$\mathbf{d}_{p}$$\mathbf{r}_{f}$$\mathbf{s}_{g}$$\mathbf{d}_{\mathrm{rec}}$$\mathbf{0}=\inf\mathcal{D}_{\mathrm{w}}$

=

?xxxX :$\mathcal{E}_{\mathrm{w}}$X :deep region of
$\mathcal{E}_{\mathrm{w}}$$\mathbf{d}_{r}$:$\mathop{\deg_{\mathrm{w}}}\bigl{(}\mathrm{LU\kern-0.50003ptA}(r)\bigr{)}$$\mathbf{d}_{\mathrm{rec}}$:$\mathop{\deg_{\mathrm{w}}}\bigl{(}\mathrm{LU\kern-0.50003ptA}_{\mathrm{rec}}\bigr{)}{=}\mathop{\deg_{\mathrm{w}}}(\mathrm{COMPLEX})$$\mathbf{d}_{\mathrm{slow}}$:
$\mathop{\deg_{\mathrm{w}}}\bigl{(}\mathrm{LU\kern-0.50003ptA}_{\mathrm{slow}}\bigr{)}$$\mathbf{s}_{h}$:$\mathop{\deg_{\mathrm{w}}}\bigl{(}\mathrm{SC}(h)\bigr{)}$$\mathbf{r}_{h}$:$\mathop{\deg_{\mathrm{w}}}\bigl{(}\mathrm{COMPLEX}(h)\bigr{)}$$L$:$\tbigcup\slimits@\\{\text{deep
$\Pi^{0}_{1}$ $P\subseteq\\{0,1\\}^{\mathbb{N}}$}\\}$
:${-}\mathrel{>_{\mathrm{w}}}{-}$:
$\mathrel{{}_{\mathrm{w}}}$-relationsx:$\mathrel{{}_{\mathrm{w}}}$-incomparable

###  I.2 Basic Conventions and Notation

$\mathbb{N}$ is the set of natural numbers (including $0$). $\mathbb{Z}$ is
the set of integers. $\mathbb{Q}$ is the set of rational numbers. $\mathbb{R}$
is the set of real numbers. Open, closed, and half-open intervals in
$\mathbb{R}$ are written $(a,b)$, $[a,b]$, and ${[a,b)},{(a,b]}$,
respectively, for any $-\infty\leq a\leq b\leq\infty$. If $\mathbb{F}$ is any
one of $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$ and
$a\in\mathbb{F}$, then we write $\mathbb{F}_{\geq
a}\mathrel{{\vdotdot}{\equal}}\\{x\in\mathbb{F}\mid a\leq x\\}$ and
$\mathbb{F}_{>a}\mathrel{{\vdotdot}{\equal}}\\{x\in\mathbb{F}\mid a<x\\}$.

$n\bmod m$ is the remainder after dividing $n$ by $m$. ${}^{m}n$ denotes the
$m$-th tetration of $n$. $\log_{2}^{k}$ denotes the composition of $k$-many
base-$2$ logarithms. $\lceil{-}\rceil$ and $\lfloor{-}\rfloor$ denote the
ceiling and floor functions, respectively. When it would increase readibility,
we write $\exp_{a}(n)=a^{n}$ for $a>0$.

Set containment is denoted by  and proper containment is denoted by  or
$\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}{$-$}}}}$}}}}$.
$\mathcal{P}(S)$ denotes the power set of $S$, while
$\mathcal{P}_{\mathrm{fin}}(S)$ denotes the set of finite subsets of $S$.
$B^{A}$ denotes the set of all functions with domain $A$ and codomain $B$.

Ordered $n$-tuples (or just ‘$n$-tuples’) are denoted using angled brackets,
as in $\langle x_{0},x_{1},x_{2},\ldots,x_{n-1}\rangle$. We assume that if
$\langle x_{0},x_{1},x_{2},\ldots,x_{n-1}\rangle=\langle
y_{0},y_{1},y_{2},\ldots,y_{m-1}\rangle$, then $n=m$. We sometimes identify an
$n$-tuple $\langle x_{0},x_{1},x_{2},\ldots,x_{n-1}\rangle$ with the set
$\\{\langle 0,x_{0}\rangle,\langle 1,x_{1}\rangle,\langle
2,x_{2}\rangle,\ldots,\langle n-1,x_{n-1}\rangle\\}$ and with the function
$f\colon\\{0,1,2,\ldots,n-1\\}\to\\{x_{0},x_{1},x_{2},\ldots,x_{n-1}\\}$
defined by $f(i)\mathrel{{\vdotdot}{\equal}}x_{i}$ for each
$i\in\\{0,1,2,\ldots,n-1\\}$. More generally, we identify a function $f\colon
A\to B$ with its graph $\\{\langle a,b\rangle\in A\times B\mid b=f(a)\\}$.

Given a function $f\colon A\to B$, we write $\operatorname{dom}f=A$ and
$\operatorname{cod}f=B$. Given subsets $A_{0}\subseteq A$ and $B_{0}\subseteq
B$, we write $f[A_{0}]\mathrel{{\vdotdot}{\equal}}\\{f(a)\mid a\in A_{0}\\}$
and $f^{-1}[B_{0}]\mathrel{{\vdotdot}{\equal}}\\{a\in A\mid f(a)\in B_{0}\\}$
for the preimage of $B_{0}$. $\operatorname{im}f$ is defined to be equal to
$f[A]$. $f{\upharpoonright}\,A_{0}$ denotes the restriction of $f$ to $A_{0}$.
If $\operatorname{dom}f=\mathbb{N}$, then we write $f{\upharpoonright}\,n$ for
the restriction $f{\upharpoonright}\,\\{0,1,2,\ldots,n-1\\}$.

If $f\colon\mathbb{N}\to\mathbb{R}$ is nondecreasing, we define
$f^{\mathrm{inv}}\colon\mathbb{R}\to\mathbb{N}$ by
$f^{\mathrm{inv}}(x)\mathrel{{\vdotdot}{\equal}}\text{least $m$ such that
$f(m)\geq x$}$.

Given functions $f,g\colon\mathbb{N}\to\mathbb{R}$, we write
$f\mathrel{{}_{\mathrm{dom}}}g$, read “$g$ _dominates_ $f$” or “$f$ is
_dominated by_ $g$” to mean that $f(n)\leq g(n)$ for almost all
$n\in\mathbb{N}$.

A _partial function_ $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0muA\to B$ is a function $f\colon A_{0}\to B$ for some $A_{0}\subseteq A$.
Given $a\in A$, then $f(a)$ is said to be _defined_ or to _converge_ , written
$f(a){\downarrow}$, if $a\in\operatorname{dom}f$, otherwise $f(a)$ is said to
be _undefined_ or _diverge_ , written $f(a){\uparrow}$. If $f\colon a\mapsto
b$, we sometimes write $f(a){\downarrow}=b$. If $f$ and $g$ are partial
functions ${\subseteq}A\to B$ and $a\in A$, then we write $f(a)\simeq g(a)$ to
mean that either $a\in\operatorname{dom}f\cap\operatorname{dom}g$ and
$f(a)=g(a)$ (i.e., $f(a)$ and $g(a)$ both converge and are equal) or that
$a\notin\operatorname{dom}f\cup\operatorname{dom}g$ (i.e., $f(a)$ and $g(a)$
both diverge). $f$ is _total_ if $\operatorname{dom}f=A$.

Given a set $S$, a _string over $S$_ – or simply a _string_ if $S$ is
understood – is any element of $S^{n}$ for some $n\in\mathbb{N}$. $S$ is the
set of all strings over $S$, i.e.,
$S=\tbigcup\slimits@_{n\in\mathbb{N}}{S^{n}}$. Given a string $\sigma\in S$,
its _length_ $|\sigma|$ is the unique $n\in\mathbb{N}$ for which $\sigma\in
S^{n}$. Given $k<|\sigma|$, $\sigma(k)$ is the $k$-th coordinate of $\sigma$,
so that $\langle\sigma(0),\sigma(1),\ldots,\sigma(|\sigma|-1)\rangle=\sigma$.
If $\sigma=\langle s_{0},s_{1},\ldots,s_{n}\rangle$ and $\tau=\langle
t_{0},t_{1},\ldots,t_{m}\rangle$ are strings over $S$, their _concatenation_
$\sigma\tau$ is given by

$\sigma\tau=\langle s_{0},s_{1},\ldots,s_{n},t_{0},t_{1},\ldots,t_{m}\rangle.$

Given $\sigma\in S$ and $n\leq|\sigma|$, $\sigma{\upharpoonright}\,n$ denotes
the string $\langle\sigma(0),\sigma(1),\ldots,\sigma(n-1)\rangle$. Given
$\sigma,\tau\in S$, then $\sigma$ is an _initial segment_ of $\tau$
(equivalently, $\tau$ is an _extension_ of $\sigma$) if
$\sigma=\tau{\upharpoonright}\,|\sigma|$, written $\sigma\subseteq\tau$.
$\sigma$ is a _proper_ initial segment of $\tau$ (equivalently, $\tau$ is a
_proper_ extension of $\sigma$) if $\sigma\subseteq\tau$ and $\sigma\neq\tau$,
written $\sigma\subset\tau$. $\sigma$ and $\tau$ are _compatible_ if either
$\sigma\subseteq\tau$ and $\tau\subseteq\sigma$, otherwise they are
_incompatible_. A set of strings $A\subseteq S$ is _prefix-free_ if
$\sigma\nsubseteq\tau$ for all distinct elements $\sigma,\tau$ in $A$. If  is
a partial order on $S$, then the _lexicographical ordering_ lex on $S$ is
defined by setting $\sigma{}_{\mathrm{lex}}\tau$ if $\sigma\subseteq\tau$ or
$\sigma(k)<\tau(k)$ for the least index $k$ at which $\sigma(k)\neq\tau(k)$.
The _shortlex ordering_ slex on $S$ is defined by setting
$\sigma{}_{\mathrm{slex}}\tau$ if $|\sigma|<|\tau|$ or if $|\sigma|=|\tau|$
and $\sigma{}_{\mathrm{lex}}\tau$, i.e., we order by length first, then
lexicographically.

Suppose $\sigma\in S$ and $f\colon\mathbb{N}\to S$ are given. $\sigma$ is an
_initial segment_ of $f$ (equivalently, $f$ is an _extension_ of $\sigma$) if
$f{\upharpoonright}\,|\sigma|=\sigma$. $\sigma$ and $f$ are _incompatible_ if
$\sigma\nsubset f$. Finally, we define $\sigma f\colon\mathbb{N}\to S$ by

$(\sigma f)(n)\mathrel{{\vdotdot}{\equal}}\begin{cases}\sigma(n)&\text{if
$n<|\sigma|$,}\\\ f(n-|\sigma|)&\text{otherwise.}\end{cases}$

The _Baire space_ $\mathbb{N}^{\mathbb{N}}$ is endowed with the topology with
basic open sets

$\left\llbracket\sigma\right\rrbracket\mathrel{{\vdotdot}{\equal}}\\{f\in\mathbb{N}^{\mathbb{N}}\mid\sigma\subset
f\\}$

for $\sigma\in\mathbb{N}$. $\mathbb{N}^{\mathbb{N}}$, with this topology, is a
non-empty zero-dimensional perfect polish space whose compact subsets have
empty interior (with these properties characterizing $\mathbb{N}^{\mathbb{N}}$
up to homeomorphism).

The _Cantor space_ $\\{0,1\\}^{\mathbb{N}}$ is endowed with the subspace
topology coming from $\mathbb{N}^{\mathbb{N}}$. Alternatively, it has the
topology with basic open sets

$\left\llbracket\sigma\right\rrbracket_{2}\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\sigma\subset
X\\}$

for $\sigma\in\\{0,1\\}$. $\\{0,1\\}^{\mathbb{N}}$, with this topology, is a
non-empty zero-dimensional compact perfect Polish space (with these properties
characterizing $\\{0,1\\}^{\mathbb{N}}$ up to homeomorphism). We make the
usual identification between elements of $\\{0,1\\}^{\mathbb{N}}$ and subsets
of $\mathbb{N}$. The _fair coin measure_ $\lambda$ is the outer measure on
$\\{0,1\\}^{\mathbb{N}}$ induced by the assignments $\lambda(\left\llbracket
A\right\rrbracket_{2})\mathrel{{\vdotdot}{\equal}}\tsum\slimits@_{i=1}^{n}{2^{-|\sigma_{i}|}}$
where $A=\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\\}\subseteq\\{0,1\\}$ is
prefix-free.

Given $f_{0},f_{1},\ldots,f_{n-1}\in\mathbb{N}^{\mathbb{N}}$, we define
$f_{0}\oplus f_{1}\oplus\@cdots\oplus f_{n-1}\in\mathbb{N}^{\mathbb{N}}$ by

$(f_{0}\oplus f_{1}\oplus\@cdots\oplus
f_{n-1})(x)\mathrel{{\vdotdot}{\equal}}f_{x\bmod n}(\lfloor x/n\rfloor).$

E.g., $(f_{0}\oplus f_{1})(2x)=f_{0}(x)$ and $(f_{0}\oplus
f_{1})(2x+1)=f_{1}(x)$. The assignment $\langle
f_{0},f_{1},\ldots,f_{n-1}\rangle\mapsto f_{0}\oplus f_{1}\oplus\@cdots\oplus
f_{n-1}$ defines a homeomorphism
$(\mathbb{N}^{\mathbb{N}})^{n}\to\mathbb{N}^{\mathbb{N}}$, and restricting to
$(\\{0,1\\}^{\mathbb{N}})^{n}$ also yields a homeomorphism
$(\\{0,1\\}^{\mathbb{N}})^{n}\to\\{0,1\\}^{\mathbb{N}}$.

For $k\geq 2$, the functions $\pi^{(k)}\colon\mathbb{N}^{k}\to\mathbb{N}$
denote the bijections defined recursively by

$\displaystyle\pi^{(2)}(x,y)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}2^{x}(2y+1)-1,$
$\displaystyle\pi^{(k+1)}(x_{1},x_{2},\ldots,x_{k},x_{k+1})$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\pi^{(2)}(\pi^{(k)}(x_{1},x_{2},\ldots,x_{k}),x_{k+1}).$

We additionally define $\pi^{(1)}\colon\mathbb{N}\to\mathbb{N}$ and
$\pi^{(0)}\colon\\{\langle\rangle\\}\to\mathbb{N}$ by setting
$\pi^{(1)}\mathrel{{\vdotdot}{\equal}}\operatorname{id}_{\mathbb{N}}$ and
$\pi^{(0)}(\langle\rangle)\mathrel{{\vdotdot}{\equal}}0$.

We define a bijection $\operatorname{str}\colon\mathbb{N}\to\\{0,1\\}$ by

$\operatorname{str}(n)=\sigma\iff
n+1=\tsum\slimits@_{i=0}^{k-1}{\sigma(i)\cdot 2^{i}}+2^{k}.$

Note that $n\leq m$ if and only if
$\operatorname{str}(n){}_{\mathrm{slex}}\operatorname{str}(m)$.

We define a bijection $\\#\colon\mathbb{N}\to\mathbb{N}$ by setting

$\\#(\sigma)\mathrel{{\vdotdot}{\equal}}\tsum\slimits@_{i=0}^{|\sigma|-1}{\exp_{2}(\sigma(0)+\sigma(1)+\@cdots+\sigma(i)+i)}.$

for each $\sigma\in\mathbb{N}$. Note that if $\sigma\subseteq\tau$, then
$\\#(\sigma)\leq\\#(\tau)$.

If $\mathbb{D}$ is an understood domain of discourse and
$S\subseteq\mathbb{D}$, then the _characteristic function for $S$_ is the
function $\chi_{S}\colon\mathbb{D}\to\\{0,1\\}$ defined by

$\chi_{S}(x)\mathrel{{\vdotdot}{\equal}}\begin{cases}1&\text{if $x\in S$,}\\\
0&\text{otherwise.}\end{cases}$

###  I.3 Computability - Definitions, Notation, and Conventions

Here we briefly review the definitions of recursiveness/computability for
various objects. With the possible exception of notation given in Section I.2
and through the remaining chapters, we have attempted to adhere to standard
notation and terminology whenever possible, so the reader is encouraged to
consult any of the standard references (e.g., [21], [31], [27], etc.) for
additional background.

####  I.3.1 (Partial) Recursive Functions and Sets

We define the collections of elementary, primitive, or partial recursive
functions as the smallest collections of partial functions
${\subseteq}\mathbb{N}^{k}\to\mathbb{N}$ closed under particular operations.

######  Definition I.3.1.

  * •

The _initial functions_ consist of the zero function
$Z\colon\mathbb{N}\to\mathbb{N}$ ($\forall
x\,(Z(x)\mathrel{{\vdotdot}{\equal}}0)$), the successor function
$S\colon\mathbb{N}\to\mathbb{N}$ ($\forall
x\,(S(x)\mathrel{{\vdotdot}{\equal}}x+1)$), and for each $k\in\mathbb{N}_{>0}$
and $j\in\\{0,1,\ldots,k-1\\}$ the projection
$\pi_{j}^{k}\colon\mathbb{N}^{k}\to\mathbb{N}$ ($\forall
x_{0},x_{1},\ldots,x_{k-1}\,(\pi_{j}^{k}(x_{0},x_{1},\ldots,x_{k-1})\mathrel{{\vdotdot}{\equal}}x_{j})$).

  * •

Given $f$ $k$-ary and $g_{1},g_{2},\ldots,g_{k}$ each $n$-ary, their
_generalized composition_ is the $n$-ary function $h$ where for
$\mathbf{x}\in\mathbb{N}^{n}$ we have

$h(\mathbf{x})\mathrel{{\vdotdot}{\equal}}f(g_{1}(\mathbf{x}),g_{2}(\mathbf{x}),\ldots,g_{k}(\mathbf{x})).$

  * •

Given $f$ $(k+1)$-ary, its _bounded sum_ and _bounded product_ are the $k$-ary
functions $g$ and $h$, respectively, where for $n\in\mathbb{N}$ and
$\mathbf{x}\in\mathbb{N}^{k}$ we have

$g(n,\mathbf{x})\mathrel{{\vdotdot}{\equal}}\tsum\slimits@_{i=0}^{n}{f(i,\mathbf{x})}\quad\text{and}\quad
h(n,\mathbf{x})\mathrel{{\vdotdot}{\equal}}\tprod\slimits@_{i=0}^{n}{f(i,\mathbf{x})}.$

  * •

Given $f$ $(k+2)$-ary and $g$ $k$-ary, the result of _primitive recursion_
applied to $f$ and $g$ is the $(k+1)$-ary function $h$ defined recursively for
$n\in\mathbb{N}$ and $\mathbf{x}\in\mathbb{N}^{k}$ by

$\displaystyle h(0,\mathbf{x})$
$\displaystyle\mathrel{{\vdotdot}{\equal}}g(\mathbf{x})$ $\displaystyle
h(n+1,\mathbf{x})$
$\displaystyle\mathrel{{\vdotdot}{\equal}}f(n,h(n,\mathbf{x}),\mathbf{x}).$

  * •

Given $f$ $(k+1)$-ary, its _minimization_ is the $k$-ary function $g$ where
for $\mathbf{x}\in\mathbb{N}^{k}$ we have

$g(\mathbf{x})\mathrel{{\vdotdot}{\equal}}\text{least $y$ such that
$f(y,\mathbf{x})=1$}.$

######  Definition I.3.2.

The collection of …

$\ldots$

_elementary recursive functions_ is the smallest collection $\mathcal{C}$ of
total functions of the form $\mathbb{N}^{k}\to\mathbb{N}$ containing the
initial functions and the function
$\dotminus\colon\mathbb{N}^{2}\to\mathbb{N}$ defined by $x\dotminus
y\mathrel{{\vdotdot}{\equal}}\max\\{x-y,0\\}$ and closed under generalized
composition and taking bounded sums and products.

$\ldots$

_primitive recursive functions_ is the smallest collection $\mathcal{C}$ of
total functions of the form $\mathbb{N}^{k}\to\mathbb{N}$ containing the
initial functions and closed under generalized composition and primitive
recursion.

$\ldots$

_partial recursive functions_ is the smallest collection $\mathcal{C}$ of
partial functions of the form ${\subseteq}\mathbb{N}^{k}\to\mathbb{N}$
containing the initial functions and closed under generalized composition,
primitive recursion, and minimization of its total members.

$\ldots$

_total recursive functions_ is the collection of total partial recursive
functions.

######  Remark I.3.3.

There are many other characterizations of the above classes. Regarding the
partial recursive functions (which are exactly the partial functions computed
by Turing machine programs or by register machine programs) Church’s Thesis
claims that any reasonable characterization of the ‘effectively computable’
partial functions is equivalent to being partial recursive.

The notion of recursiveness is extended to subsets of $\mathbb{N}^{k}$:

######  Definition I.3.4 (recursive predicate).

A predicate $S\subseteq\mathbb{N}^{k}$ is _recursive_ if its characteristic
function $\chi_{S}\colon\mathbb{N}^{k}\to\\{0,1\\}$ is recursive.

To extend the notion of partial recursiveness to partial functions whose
domains or codomains are not $\mathbb{N}^{k}$ for some $k$, we make use of
Gödel numbers.

######  Definition I.3.5.

Suppose $S$ and $T$ are countable sets $S$ and $T$ and then fix injections
$\\#_{S}\colon S\to\mathbb{N}$ and $\\#_{T}\colon T\to\mathbb{N}$ for which
$\operatorname{im}\\#_{S}$ and $\operatorname{im}\\#_{T}$ are both recursive
subsets of $\mathbb{N}$, which we informally call _Gödel numberings_ of $S$
and $T$, respectively. Then a partial function $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0muS\to T$ is _partial recursive_ (with respect to $\\#_{S}$ and $\\#_{T}$)
if the partial function $\\#_{T}\circ f\circ\\#_{S}^{-1}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ is partial recursive.

######  Convention I.3.6.

Unless stated otherwise, we assume the following Gödel numberings:

#(

s0,s1,…,sk-1)

, where $T=\\{s_{0},s_{1},\ldots,s_{k-1}\\}$ and
$\\#(s_{0})<\\#(s_{1})<\@cdots<\\#(s_{k-1})$. • $\mathbb{Z}$ is Gödel numbered
by setting $\\#_{\mathbb{Z}}(n)\mathrel{{\vdotdot}{\equal}}2n$ if $n\geq 0$
and $\\#_{\mathbb{Z}}(n)\mathrel{{\vdotdot}{\equal}}2n+1$ if $n<0$. •
$\mathbb{Q}$ is Gödel numbered by setting
$\\#_{\mathbb{Q}}(r)\mathrel{{\vdotdot}{\equal}}\pi^{(2)}(n,m)$, where if
$r=p/q$ with $\gcd(p,q)=1$ and $q\geq 1$ then $n=\\#_{\mathbb{Z}}(p)$ and $q$
is the $m$-th positive integer coprime with $p$.

######  Remark I.3.7.

Under any reasonable Gödel numberings, such as in Convention I.3.6, relevant
operations and relations on the Gödel numbered objects yield recursive
operations and relations on their Gödel numbers. E.g., for strings (either in
$\mathbb{N}$ or $\\{0,1\\}$), this includes for operations the length and
concatenation functions and for relations the the lexicographical ordering,
the shortlex ordering, and ; for integers and rationals, this includes
virtually all number theoretic operations, the standard total orderings, and
the divisibility relation. In some cases our choices of Gödel numberings are
purposeful, as in the cases of $\pi^{(k)}$ and $\\#_{2}$. Unless otherwise
stated, we have chosen particular Gödel numberings for the remaining cases
solely for exactness, and in principle the reader may substitute them with
their preferred encodings.

####  I.3.2 Enumerations of the Partial Recursive Functions

Thanks to their connection to effective algorithms, a partial recursive
function $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{k}\to\mathbb{N}$ can be described by a single natural number
$e$ which we may think of as encoding an algorithm computing $\theta$.

######  Definition I.3.8 (effective enumeration).

An _enumeration_ $\varphi_{0},\varphi_{1},\varphi_{2},\ldots$ of the $k$-place
partial recursive functions is any surjection from $\mathbb{N}$ onto the set
of all $k$-place partial recursive functions $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{k}\to\mathbb{N}$. Such an enumeration is _effective_ if the
partial function
$\Phi(e,x_{1},x_{2},\ldots,x_{k})\simeq\varphi_{e}(x_{1},x_{2},\ldots,x_{k})$
is partial recursive.

######  Convention I.3.9.

Unless otherwise specified, $\varphi_{0},\varphi_{1},\varphi_{2},\ldots$ will
be an enumeration of the $1$-place partial recursive functions. For concision,
$\varphi$ will denote an enumeration
$\varphi_{0},\varphi_{1},\varphi_{2},\ldots$.

Given an enumeration $\varphi$ and $k\in\mathbb{N}_{\geq 1}$, we denote by
$\varphi^{(k)}$ the enumeration of the $k$-place partial recursive functions
defined by
$\varphi_{e}^{(k)}(x_{1},\ldots,x_{k})\simeq\varphi_{e}(\pi^{(k)}(x_{1},\ldots,x_{k}))$
for all $e,x_{1},\ldots,x_{k}\in\mathbb{N}$.

For many purposes, an enumeration $\varphi$ satisfying stronger properties
than simply being effective is required. An example of such a property is that
the $S^{m}_{n}$ Theorem holds:

######  Property I.3.10 ($S^{m}_{n}$ Theorem).

For all $m,n\in\mathbb{N}$ there exists a primitive222It is essential that
$\pi^{(k)}\colon\mathbb{N}^{k}\to\mathbb{N}$ be primitive recursive for each
$k$ so that the fulfillment of the $S^{m}_{n}$ Theorem (particularly, the
primitive recursiveness of $S^{m}_{n}$) does not depend on the choice of
$\pi^{(k)}$ for $k\in\mathbb{N}$. recursive function
$S^{m}_{n}\colon\mathbb{N}^{m+1}\to\mathbb{N}$ such that
$\varphi_{S^{m}_{n}(e,x_{1},\ldots,x_{m})}^{(n)}(y_{1},\ldots,y_{n})\simeq\varphi_{e}^{(m+n)}(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})$
for all $e,x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}\in\mathbb{N}$.

A weaker version that often suffices for application (and does for our uses)
is the following.

######  Property I.3.11 (Parametrization Theorem).

For any partial recursive function $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{2}\to\mathbb{N}$, there exists a total recursive function
$f\colon\mathbb{N}\to\mathbb{N}$ such that
$\varphi_{f(e)}(x)\simeq\theta(e,x)$ for all $e,x\in\mathbb{N}$.

The Parametrization Theorem has further implications.

######  Proposition I.3.12.

(well-known) Suppose $\varphi$ is an effective enumeration for which the
Parametrization Theorem holds.

  1. (a)

For all $m,n\in\mathbb{N}$ there exists a total recursive function
$S^{m}_{n}\colon\mathbb{N}^{m+1}\to\mathbb{N}$ such that

$\varphi_{S^{m}_{n}(e,x_{1},\ldots,x_{m})}^{(n)}(y_{1},\ldots,y_{n})\simeq\varphi_{e}^{(m+n)}(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})$

for all $e,x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}\in\mathbb{N}$.

  2. (b)

Recursion Theorem: For any partial recursive function $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{n+1}\to\mathbb{N}$ there exists an $e\in\mathbb{N}$ such that
$\varphi_{e}^{(n)}(x_{1},\ldots,x_{n})\simeq\theta(e,x_{1},\ldots,x_{n})$ for
all $x_{1},\ldots,x_{n}\in\mathbb{N}$.

The Parametrization _Theorem_ is stated as a property of a enumeration rather
than a feature of all effective enumerations due to the following observation.

######  Definition I.3.13 (admissible enumeration).

An enumeration $\varphi$ is _admissible_ if it is effective and for which the
Parametrization Theorem holds.

######  Proposition I.3.14.

[20, following Definition 3] There exists an effective enumeration $\varphi$
which is not admissible.

In [20], Rogers examines the relationships between different enumerations of
the partial recursive functions333Within [20], Rogers uses the term
‘numbering’ where we use ‘enumeration’ and ‘semi-effective’ where we use
‘effective’.. There, an enumeration is defined as a surjection $\rho$ from a
recursive subset $D_{\rho}$ of $\mathbb{N}$ onto the set of all $1$-place
partial recursive functions. ‘Effectiveness’ is defined as above, and the only
modification necessary for ‘admissibility’ is that the total recursive
function $f$ in the statement of the Parametrization Theorem take values in
$D_{\rho}$.

######  Definition I.3.15.

Suppose $\rho$ and $\tau$ are enumerations. We write $\rho\preceq\tau$ if
there is a recursive function $g\colon D_{\rho}\to D_{\tau}$ such that
$\rho=\tau\circ g$.

######  Lemma I.3.16.

is a preorder on the set of all effective enumerations.

######  Proposition I.3.17.

[30, Exercise 5.10] Suppose $\tau$ is an admissible enumeration. Then $\tau$
is admissible if and only if $\rho\preceq\tau$ for any effective enumeration
$\rho$.

###### Proof.

Suppose $\rho$ is an effective enumeration. It suffices to show that if $\tau$
is admissible, then  (i) $\rho\preceq\tau$, and  (ii) if $\tau\preceq\rho$,
then $\rho$ is admissible.

Suppose $\tau$ is admissible. $\rho$ is an effective enumeration, so the
partial function $\Phi(e,x)\simeq\rho(e)(x)$ is recursive. Because $\tau$ is
admissible, there exists a total recursive function $f\colon\mathbb{N}\to
D_{\tau}$ such that $\tau(f(e))(x)\simeq\Phi(e,x)$ for all $e,x\in\mathbb{N}$,
or equivalently that $\tau\circ f=\rho$. Thus, $\rho\preceq\tau$.

Now suppose $\tau\preceq\rho$, so that there is a total recursive function
$g\colon D_{\tau}\to D_{\rho}$ such that $\tau=\rho\circ g$. Suppose
$\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{2}\to\mathbb{N}$ is any partial recursive function. Because
$\tau$ is admissible, there exists a total recursive function
$f\colon\mathbb{N}\to\mathbb{N}$ such that $\tau(f(e))(x)\simeq\theta(e,x)$
for all $e,x\in\mathbb{N}$. But then $\rho((g\circ f)(e))(x)\simeq\theta(e,x)$
for all $e,x\in\mathbb{N}$, showing $\rho$ is admissible. ∎

######  Corollary I.3.18.

Let $E$ denote the set of effective enumerations, let be the equivalence
relation induced by (i.e., $\rho\cong\tau$ if and only if $\rho\preceq\tau$
and $\tau\preceq\rho$), and let be the partial order on $E/{\cong}$ induced by
(i.e., $\rho/{\cong}\leq\tau/{\cong}$ if and only if $\rho\preceq\tau$). Then
the poset $(E/{\cong},\leq)$ has a maximum, and that maximum is equal to the
set of all admissible enumerations.

######  Remark I.3.19.

All standard enumerations of the $1$-place partial recursive functions are
admissible.

######  Convention I.3.20.

Unless otherwise specified, any effective enumeration $\varphi$ used is
assumed to be admissible. Given a partial recursive $\theta$, an _index for
$\theta$_ is any $e\in\mathbb{N}$ for which $\theta=\varphi_{e}$.

Many admissible enumerations have a natural way to interpret the statement,
“$\varphi_{e}(x)$ converges to $y$ within $s$ steps.”

######  Notation I.3.21.

Given an admissible enumeration $\varphi$ of the $k$-place partial recursive
functions, the notation $\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k})$ is used to
denote the output of a partial recursive function $\langle
e,x_{1},x_{2},\ldots,x_{k},s\rangle\mapsto\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k})$
satisfying the following properties:

  1. (a)

$\varphi_{e}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$ if and only if
$\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$ for some
$s\in\mathbb{N}$, in which case
$\varphi_{e}(x_{1},x_{2},\ldots,x_{k})=\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k})$.

  2. (b)

If $s<t$ and $\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$, then
$\varphi_{e,t}(x_{1},x_{2},\ldots,x_{k}){\downarrow}=\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k})$.

  3. (c)

The set $\\{\langle
e,x_{1},x_{2},\ldots,x_{k},s\rangle\mid\varphi_{e,s}(x_{1},x_{2},\ldots,x_{k}){\downarrow}\\}$
is recursive.444In contrast, $\\{\langle
e,x_{1},x_{2},\ldots,x_{k}\rangle\mid\varphi_{e}(x_{1},x_{2},\ldots,x_{k}){\downarrow}\\}$
is nonrecursive and in fact
$\\{\pi^{(k+1)}(e,x_{1},x_{2},\ldots,x_{k})\mid\varphi_{e}(x_{1},x_{2},\ldots,x_{k}){\downarrow}\\}$
is many-one equivalent to the Halting Problem.

####  I.3.3 Partial Recursive Functionals

Although $\\{0,1\\}^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$ cannot be
Gödel numbered, reasoning about initial segments of sequences in
$\\{0,1\\}^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$ allows us to talk about
partial recursiveness for partial functions involving these spaces.

######  Proposition I.3.22.

(well-known) Suppose $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ is given. The
following are equivalent.

  1. (i)

There exists a partial recursive function $\Gamma_{1}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that

$\forall\sigma\forall\sigma^{\prime}\forall x\forall
y\,\bigl{(}(\langle\sigma,x,y\rangle\in\Gamma_{1}\wedge\sigma\subseteq\sigma^{\prime})\implies\langle\sigma^{\prime},x,y\rangle\in\Gamma_{1}\bigr{)}$

for which $\Psi(X)\simeq Y$ if and only if $\forall x\exists n\,\langle
X{\upharpoonright}\,n,x,Y(x)\rangle\in\Gamma_{1}$.

  2. (ii)

There exists a partial recursive function $\Gamma_{2}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that

$\forall\sigma\forall\sigma^{\prime}\forall
x\,\bigl{(}(\langle\sigma,x\rangle\in\operatorname{dom}\Gamma_{2}\wedge\langle\sigma^{\prime},x\rangle\in\operatorname{dom}\Gamma_{2}\wedge\sigma\subseteq\sigma^{\prime})\implies\sigma=\sigma^{\prime}\bigr{)}$

for which $\Psi(X)\simeq Y$ if and only if $\forall x\exists x\,\langle
X{\upharpoonright}\,n,x,Y(x)\rangle\in\Gamma_{2}$.

  3. (iii)

There exists a partial recursive function $\Gamma_{3}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ such that

$\forall\sigma\forall\sigma^{\prime}\forall\tau\forall\tau^{\prime}\,\bigl{(}(\langle\sigma,\tau\rangle\in\Gamma_{3}\wedge\langle\sigma^{\prime},\tau^{\prime}\rangle\in\Gamma_{3}\wedge\sigma\subseteq\sigma^{\prime})\implies(\tau\subseteq\tau^{\prime}\vee\tau^{\prime}\subseteq\tau)\bigr{)}$

for which $\Psi(X)\simeq Y$ if and only if
$Y\simeq\tbigcup\slimits@\\{\tau\mid\exists\sigma\subset
X\,(\langle\sigma,\tau\rangle\in\Gamma_{3})\\}$.

######  Definition I.3.23 (partial recursive functional).

A partial functional $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ is _partial recursive_
if any (equivalently, all) of the conditions in Proposition I.3.22 hold.

######  Notation I.3.24.

We will implicitly identify a partial recursive functional $\Psi$ with a
partial recursive function $\Gamma_{\Psi}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ as in Proposition I.3.22(iii). We define:

$\displaystyle\Psi^{X}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@\\{\tau\in\mathbb{N}\mid\exists\sigma\subset
X\,(\langle\sigma,\tau\rangle\in\Gamma_{\Psi})\\}$ for
$X\in\mathbb{N}^{\mathbb{N}}$, $\displaystyle\Psi^{-1}(\sigma)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid\Psi^{X}\supseteq\sigma\\}=\left\llbracket\\{\tau\in\mathbb{N}\mid\exists\sigma^{\prime}\supseteq\sigma\,(\langle\tau,\sigma^{\prime}\rangle\in\Gamma_{\Psi})\\}\right\rrbracket$
for $\sigma\in\mathbb{N}$, and $\displaystyle\Psi^{-1}(S)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@_{\sigma\in
S}{\Psi^{-1}(\sigma)}$ for $S\subseteq\mathbb{N}$.

Note that $\Psi^{X}$ is a member of $\mathbb{N}\cup\mathbb{N}^{\mathbb{N}}$,
and that $\Psi^{X}\in\mathbb{N}^{\mathbb{N}}$ if and only if
$X\in\operatorname{dom}\Psi$, in which case $\Psi(X)=\Psi^{X}$.

For partial functions of the form $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell}\to(\mathbb{N}^{\mathbb{N}})^{m}\times\mathbb{N}^{n}$
($k,m\geq 1$) to be partial recursive, we may either make appropriate
adjustments to the above definitions, or reduce to the case
${\subseteq}\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ by associating
a tuple $\langle
X_{0},X_{1},\ldots,X_{k-1},x_{0},x_{1},\ldots,x_{\ell-1}\rangle$ with $\langle
x_{0},x_{1},\ldots,x_{\ell-1}\rangle(X_{0}\oplus X_{1}\oplus\@cdots\oplus
X_{k-1})$.

####  I.3.4 The Arithmetical Hierarchy

The arithmetical hierarchy provides one stratification of the complexity of
subsets of $(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell}$, and
although we will only be interested in very low levels of that hierarchy, it
is more convenient to define the general notion than those individual levels
separately.

######  Definition I.3.25 (arithmetical hierarchy).

A subset $S\subseteq(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell}$ is
$\Sigma^{0}_{0}$ and $\Pi^{0}_{0}$ if $S$ is recursive. Given $\Sigma^{0}_{n}$
and $\Pi^{0}_{n}$ have been defined, we say that $S$ is $\Sigma^{0}_{n+1}$ if
there exists a $\Pi^{0}_{n}$ subset
$R\subseteq(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell+1}$ such that

$S(X_{1},\ldots,X_{k},y_{1},\ldots,y_{\ell})\equiv\exists
m\,R(X_{1},\ldots,X_{k},y_{1},\ldots,y_{\ell},m).$

for all $X_{1},\ldots,X_{k}\in\mathbb{N}^{\mathbb{N}}$ and
$y_{1},\ldots,y_{\ell}\in\mathbb{N}$. Likewise, $S$ is $\Pi^{0}_{n+1}$ if
there exists a $\Sigma^{0}_{n}$ subset
$R\subseteq(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell+1}$ such that

$S(X_{1},\ldots,X_{k},y_{1},\ldots,y_{\ell})\equiv\forall
m\,R(X_{1},\ldots,X_{k},y_{1},\ldots,y_{\ell},m)$

for all $X_{1},\ldots,X_{k}\in\mathbb{N}^{\mathbb{N}}$ and
$y_{1},\ldots,y_{\ell}\in\mathbb{N}$.

Other names are given to the lowest nontrivial level of the arithmetical
hierarchy for subsets of $\mathbb{N}^{k}$.

######  Definition I.3.26 ((co-)recursively enumerable).

A subset $X\subseteq\mathbb{N}^{k}$ is _recursively enumerable_ , or _r.e._ ,
if $X$ is $\Sigma^{0}_{1}$, and _co-recursively enumerable_ , or _co-r.e._ ,
if $X$ is $\Pi^{0}_{1}$.

######  Remark I.3.27.

More generally, we can extend the use of ‘r.e.’ and ‘co-r.e.’ to sets of
objects which are Gödel numbered. In particular, it makes sense to speak of a
set of strings $S\subseteq\mathbb{N}$ being r.e. or co-r.e.

Often we are interested in sequences of sets each of which is at the same
level of the arithmetical hierarchy in a uniform way.

######  Definition I.3.28 (uniformly $\Sigma^{0}_{n}$/$\Pi^{0}_{n}$).

A sequence $\langle S_{i}\rangle_{i\in I}$ of subsets
$S_{i}\subseteq(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell}$ is
_uniformly $\Sigma^{0}_{n}$_ (respectively, _uniformly $\Pi^{0}_{n}$_) if it
is $\Sigma^{0}_{n}$ (resp., $\Pi^{0}_{n}$) when considered as a subset of
$(\mathbb{N}^{\mathbb{N}})^{k}\times\mathbb{N}^{\ell+1}$.

####  I.3.5 Recursive Reals and Real-Valued Functions

Like $\\{0,1\\}^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$, although
$\mathbb{R}$ cannot be Gödel numbered, we can reason about real-valued
functions by approximating real outputs by recursive sequences of rational
numbers.

######  Definition I.3.29 (recursive/computable real).

$\alpha\in\mathbb{R}$ is _left recursively enumerable_ , or _left r.e._ , if
there is a recursive sequence $\langle p_{n}\rangle_{n\in\mathbb{N}}$ of
rational numbers converging monotonically to $\alpha$ from below.

$\alpha$ is _right recursively enumerable_ , or _right r.e._ , if there is a
recursive sequence $\langle q_{n}\rangle_{n\in\mathbb{N}}$ of rational numbers
converging monotonically to $\alpha$ from above.

If $\alpha$ is both left r.e. and right r.e., then $\alpha$ is _recursive_ or
_computable_.

######  Lemma I.3.30.

(well-known) Suppose $\alpha$ is a real number.

  1. (a)

$\alpha$ is recursive if and only if there exists a monotone recursive
sequence $\langle\alpha_{k}\rangle_{k\in\mathbb{N}}$ of rational numbers such
that $|\alpha-\alpha_{k}|\leq 2^{-k}$ for each $k\in\mathbb{N}$.

  2. (b)

$\alpha$ is left r.e. if and only if there exists a sequence
$\langle\alpha_{k}\rangle_{k\in\mathbb{N}}$ of uniformly recursive reals
$\alpha_{k}\leq\alpha$ converging to $r$.

  3. (c)

$\alpha$ is right r.e. if and only if there exists a sequence
$\langle\alpha_{k}\rangle_{k\in\mathbb{N}}$ of uniformly recursive reals
$\alpha_{k}\geq\alpha$ converging to $\alpha$.

###### Proof.

Straight-forward. ∎

######  Definition I.3.31 (recursive/computable real-valued function of a
discrete variable).

$f\colon\mathbb{N}\to\mathbb{R}$ is _left recursively enumerable_ , or _left
r.e._ , if there is a recursive function
$p_{-,-}\colon\mathbb{N}^{2}\to\mathbb{Q}$ such that for each
$x\in\mathbb{N}$, the sequence $\langle p_{n,x}\rangle_{n\in\mathbb{N}}$
converges monotonically to $f(x)$ from below.

$f$ is _right recursively enumerable_ , or _right r.e._ , if there is a
recursive funciton $q_{-,-}\colon\mathbb{N}^{2}\to\mathbb{Q}$ such that for
each $x\in\mathbb{N}$, the sequence $\langle q_{n,x}\rangle_{n\in\mathbb{N}}$
converges monotonically to $f(x)$ from above.

If $f$ is both left r.e. and right r.e., then $f$ is _recursive_ or
_computable_.

######  Remark I.3.32.

In the definitions of left r.e., right r.e., and recursive functions
$f\colon\mathbb{N}\to\mathbb{R}$, we may replace $\mathbb{N}$ with any set $S$
which can be Gödel numbered, associating a function $g\colon S\to\mathbb{R}$
with the function $g\circ\\#^{-1}\colon\mathbb{N}\to\mathbb{R}$, where
$\\#\colon S\to\mathbb{N}$ is a Gödel numbering.

One of the principal ways in which recursive real-valued functions appear is
to quantify growth rate.

######  Definition I.3.33 (order function).

An _order function_ is a function $f\colon\mathbb{N}\to\mathbb{R}$ which is
nondecreasing, unbounded, and computable.

Now we describe what it means for a real-valued function of a real variable to
be computable.

######  Definition I.3.34 (recursive/computable real-valued function of a real
variable).

A function $\chi\colon\mathbb{N}\to\mathbb{Q}$ _represents_ $x\in\mathbb{R}$
if $|\chi(n)-x|\leq 2^{-n}$ for all $n\in\mathbb{N}$.

Suppose $I\subseteq\mathbb{R}$ is an interval. A function $f\colon
I\to\mathbb{R}$ is _recursive_ or _computable_ if there exists a partial
recursive functional $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{Q}^{\mathbb{N}}\to\mathbb{Q}^{\mathbb{N}}$ such that whenever
$\chi\colon\mathbb{N}\to\mathbb{Q}$ represents $x\in I$ and
$\operatorname{im}\chi\subseteq I$, $\Psi(\chi){\downarrow}$ and $\Psi(\chi)$
represents $f(x)$.

######  Remark I.3.35.

By ‘interval’ we include both the bounded intervals ${(a,b)}$, ${[a,b)}$,
${(a,b]}$, $[a,b]$, and the unbounded intervals $(-\infty,\infty)$,
${[a,\infty)}$, ${(-\infty,b]}$, $(a,\infty)$, $(-\infty,b)$.

We will assume the following basic facts concerning computable real-valued
functions of a real variable.

######  Proposition I.3.36.

(well-known)

  1. (a)

The functions $x\mapsto\alpha$, $x\mapsto x^{\beta}$, $x\mapsto\log_{2}x$,
$x\mapsto 2^{x}$, and $x\mapsto\lfloor x\rfloor$ are computable, where each
function has its natural domain and $\alpha\in\mathbb{R}$ and
$\beta\in\mathbb{R}_{\geq 0}$ are computable.

  2. (b)

If $f\colon\mathbb{N}\to\mathbb{R}$ is computable, then the piecewise-linear
extension $\overline{f}\colon{[0,\infty)}\to\mathbb{R}$ defined by
$\overline{f}(x)\mathrel{{\vdotdot}{\equal}}(f(\lfloor x\rfloor+1)-f(\lfloor
x\rfloor))(x-\lfloor x\rfloor)+f(\lfloor x\rfloor)$ for each
$x\in{[0,\infty)}$ is computable.

  3. (c)

If $f\colon{[0,\infty)}\to\mathbb{R}$ is computable, then
$f{\upharpoonright}\,\mathbb{N}$ is computable.

  4. (d)

If $f\colon I\to\mathbb{R}$ is computable and $J$ is an interval whose
endpoints are either infinite or finite, computable reals, then
$f{\upharpoonright}\,(I\cap J)$ is computable.

  5. (e)

If $f,g\colon I\to\mathbb{R}$ are computable, then $f+g$ and $f\cdot g$ are
computable.

  6. (f)

If $f\colon I\to\mathbb{R}$ and $g\colon J\to\mathbb{R}$ are computable and
$\operatorname{im}f\subseteq J$, then their composition $g\circ f$ is
computable.

###### Proof.

Cumbersome but routine. ∎

###  I.4 Reducibility Notions

####  I.4.1 Turing Reducibility

The principal way to measure the ‘degree of unsolvability’ of an infinite
sequence $X\in\mathbb{N}^{\mathbb{N}}$ is Turing reducibility.

######  Theorem I.4.1.

(well-known) Suppose $X,Y\in\mathbb{N}^{\mathbb{N}}$. The following are
equivalent.

  1. (i)

$X$ is a member of the smallest collection of partial functions
${\subseteq}\mathbb{N}^{k}\to\mathbb{N}$ containing the initial functions,
containing $Y$, and closed under generalized composition, primitive recursion,
and minimization.

  2. (ii)

There exists an oracle Turing machine which computes $X$ given an oracle for
$Y$.

  3. (iii)

There exists an oracle register machine program which computes $X$ given an
oracle for $Y$.

  4. (iv)

There exists a recursive functional $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$ such that
$\Psi(Y){\downarrow}=X$.

######  Definition I.4.2 (Turing reducibility).

Given $X,Y\in\mathbb{N}^{\mathbb{N}}$, we say that $X$ is _Turing reducible_
to $Y$, written $X\mathrel{{}_{\mathrm{T}}}Y$, if any of the equivalent
conditions in Theorem I.4.1 hold. We may also say that $X$ is _$Y$
-computable_, _$Y$ -recursive_, or that _$Y$ computes $X$_.

If $X\mathrel{{}_{\mathrm{T}}}Y$ and $Y\mathrel{{}_{\mathrm{T}}}X$, then we
say that $X$ and $Y$ are _Turing equivalent_ and write
$X\mathrel{{}_{\mathrm{T}}}Y$.

$\mathrel{{}_{\mathrm{T}}}$ is a preorder, and hence
$\mathrel{{}_{\mathrm{T}}}$ is an equivalence relation.

######  Definition I.4.3 (Turing degree).

The _Turing degree_ of an infinite sequence $X\in\mathbb{N}^{\mathbb{N}}$ is
the $\mathrel{{}_{\mathrm{T}}}$-equivalence class containing $X$, written
$\mathop{\deg_{\mathrm{T}}}(X)$.

The collection of all Turing degrees is written $\mathcal{D}_{\mathrm{T}}$.
$\mathrel{{}_{\mathrm{T}}}$ induces a partial order on
$\mathcal{D}_{\mathrm{T}}$ defined by setting
$\mathop{\deg_{\mathrm{T}}}(X)\leq\mathop{\deg_{\mathrm{T}}}(Y)$ if and only
if $X\mathrel{{}_{\mathrm{T}}}Y$.

######  Example I.4.4.

$\mathbf{0}$ is the Turing degree of any recursive
$X\in\mathbb{N}^{\mathbb{N}}$. It is the minimum of
$\mathcal{D}_{\mathrm{T}}$.

######  Example I.4.5.

Consider the following subsets of $\mathbb{N}$, which we tacitly identify with
their characteristic functions:

$\displaystyle H_{1}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{e\in\mathbb{N}\mid\varphi_{e}(0){\downarrow}\\},$
$\displaystyle H_{2}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{e\in\mathbb{N}\mid\varphi_{e}(e){\downarrow}\\},$
$\displaystyle H_{3}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{e\in\mathbb{N}\mid\text{$\varphi_{i}(n){\downarrow}$,
where $\pi^{(2)}(i,n)=e$}\\}.$

All three Turing equivalent to one another. Firstly,
$H_{1}\mathrel{{}_{\mathrm{T}}}H_{3}$ because $e\in H_{1}$ if and only if
$\pi^{(2)}(e,0)\in H_{3}$; likewise, $H_{2}\mathrel{{}_{\mathrm{T}}}H_{3}$
because $e\in H_{1}$ if and only if $\pi^{(2)}(e,e)\in H_{3}$. For the
opposite direction, consider the partial recursive function
$\theta(\pi^{(2)}(i,n),m)\simeq\varphi_{i}(n)$; the Parametrization Theorem
yields a total recursive function $f\in\mathbb{N}^{\mathbb{N}}$ such that
$\varphi_{f(e)}(m)\simeq\theta(e,m)$ for all $e,m\in\mathbb{N}$. Then

$e\in H_{3}\iff f(e)\in H_{1}\iff f(e)\in H_{2},$

showing $H_{3}\mathrel{{}_{\mathrm{T}}}H_{1}$ and
$H_{3}\mathrel{{}_{\mathrm{T}}}H_{2}$. $H_{3}$ is the Halting problem, though
thanks to the above equivalences we may also refer to $H_{1}$ or $H_{2}$ as
the Halting problem. The Turing degree of
$H_{1}\mathrel{{}_{\mathrm{T}}}H_{2}\mathrel{{}_{\mathrm{T}}}H_{3}$ is called
$\mathbf{0}^{\prime}$ and $X\in\mathbb{N}^{\mathbb{N}}$ is said to be
_complete_ if $\mathbf{0}^{\prime}\leq\mathop{\deg_{\mathrm{T}}}(X)$.

Some simple facts about Turing degrees include the following:

######  Lemma I.4.6.

Suppose $X,Y\in\mathbb{N}^{\mathbb{N}}$ are given.

  1. (a)

$\mathop{\deg_{\mathrm{T}}}(X\oplus
Y)=\sup\\{\mathop{\deg_{\mathrm{T}}}(X),\mathop{\deg_{\mathrm{T}}}(Y)\\}$.
Consequently, $(\mathcal{D}_{\mathrm{T}},\leq)$ is a join semi-lattice.

  2. (b)

There exists $Z\in\\{0,1\\}^{\mathbb{N}}$ such that
$X\mathrel{{}_{\mathrm{T}}}Z$.

###### Proof.

Straight-forward. ∎

In analogy with admissible enumerations of the $k$-place partial recursive
functions we may also consider admissible enumerations of the $k$-place
partial recursive functionals
${\subseteq}\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{k}\to\mathbb{N}$.

######  Definition I.4.7 (admissible enumeration of partial recursive
functionals).

An _admissible enumeration_ of the $k$-place partial recursive functionals
${\subseteq}\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{k}\to\mathbb{N}$ is a
sequence $\Phi_{0},\Phi_{1},\Phi_{2},\ldots$ of such functionals such that:

  1. (i)

For every partial recursive functional $\Psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{k}\to\mathbb{N}$ there is
$e\in\mathbb{N}$ such that $\Psi=\Phi_{e}$.

  2. (ii)

The partial functional
$\Phi(e,X,x_{1},x_{2},\ldots,x_{k})\simeq\Phi_{e}(X,x_{1},x_{2},\ldots,x_{k})$
is partial recursive.

  3. (iii)

For any partial recursive functional $\Theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{k+1}\to\mathbb{N}$ there exists
a total recursive $g\colon\mathbb{N}\to\mathbb{N}$ such that, for all
$f\in\mathbb{N}^{\mathbb{N}}$ and $e,x_{1},x_{2},\ldots,x_{k}\in\mathbb{N}$,

$\Phi_{g(e)}(f,x_{1},x_{2},\ldots,x_{k})\simeq\Theta(f,e,x_{1},x_{2},\ldots,x_{k}).$

######  Notation I.4.8.

The notation $\langle
X,e,x_{1},x_{2},\ldots,x_{k}\rangle\mapsto\varphi_{e}^{X}(x_{1},x_{2},\ldots,x_{k})$
will often be used to denote an (admissible) enumeration of the $k$-place
partial recursive functionals
${\subseteq}\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{k}\to\mathbb{N}$.

The notation $\varphi_{e,s}^{\tau}(x_{1},x_{2},\ldots,x_{k})$ is used to
denote the output of a partial recursive function

$\langle
e,x_{1},x_{2},\ldots,x_{k},s,\tau\rangle\mapsto\varphi_{e,s}^{\tau}(x_{1},x_{2},\ldots,x_{k})$
satisfying the following properties:

  1. (i)

For every $X\in\mathbb{N}^{\mathbb{N}}$,
$\varphi_{e}^{X}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$ if and only if
$\varphi_{e,s}^{X{\upharpoonright}\,s}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$
for some $s\in\mathbb{N}$, in which case
$\varphi_{e}^{X}(x_{1},x_{2},\ldots,x_{k})=\varphi_{e,s}^{X{\upharpoonright}\,s}(x_{1},x_{2},\ldots,x_{k})$.

  2. (ii)

If $\sigma\subseteq\tau$, $s\leq t$, and
$\varphi_{e,s}^{\sigma}(x_{1},x_{2},\ldots,x_{k}){\downarrow}$, then
$\varphi_{e,t}^{\tau}(x_{1},x_{2},\ldots,x_{k}){\downarrow}=\varphi_{e,s}^{\sigma}(x_{1},x_{2},\ldots,x_{k})$.

  3. (iii)

The set $\\{\langle
e,x_{1},x_{2},\ldots,x_{k},s,\tau\rangle\mid\varphi_{e,s}^{\tau}(x_{1},x_{2},\ldots,x_{k}){\downarrow}\\}$
is recursive.

####  I.4.2 Mass Problems and Weak, Strong Reducibility

When measuring the ‘degree of unsolvability’ of a _subset_ of
$\mathbb{N}^{\mathbb{N}}$ there are two notions of reducibility we consider.

######  Definition I.4.9 (weak reducibility).

Given $P,Q\subseteq\mathbb{N}^{\mathbb{N}}$, $P$ is _weakly reducible_ to $Q$,
written $P\mathrel{{}_{\mathrm{w}}}Q$, if for every $Y\in Q$ there exists
$X\in Q$ such that $X\mathrel{{}_{\mathrm{T}}}Y$.

If $P\mathrel{{}_{\mathrm{w}}}Q$ and $Q\mathrel{{}_{\mathrm{w}}}P$, then $P$
and $Q$ are _weakly equivalent_ , written $P\mathrel{{}_{\mathrm{w}}}Q$.

######  Definition I.4.10 (strong reducibility).

Given $P,Q\subseteq\mathbb{N}^{\mathbb{N}}$, $P$ is _strongly reducible_ to
$Q$, written $P\mathrel{{}_{\mathrm{s}}}Q$, if there exists a recursive
functional $\Psi\colon Q\to P$.

If $P\mathrel{{}_{\mathrm{s}}}Q$ and $Q\mathrel{{}_{\mathrm{w}}}P$, then $P$
and $Q$ are _strongly equivalent_ , written $P\mathrel{{}_{\mathrm{s}}}Q$.

######  Remark I.4.11.

Weak reducibility is also called _Muchnik reducibility_ , and strong
reducibility is also called _Medvedev reducibility_.

An interpretation of a subset $P\subseteq\mathbb{N}^{\mathbb{N}}$ is as a
_problem_ (and within this context subsets of $\mathbb{N}^{\mathbb{N}}$ are
sometimes called _mass problems_) whose elements are its _solutions_. If
$P\mathrel{{}_{\mathrm{w}}}Q$, then any solution to $Q$ computes a solution to
$P$, though this is not necessarily a uniform procedure. If
$P\mathrel{{}_{\mathrm{s}}}Q$, then there is a uniform procedure to turn a
solution to $Q$ into a solution to $P$. See [25] and [24] for additional
information and motivation.

As with Turing reducibility, both weak and strong reducibility are preorders
on $\mathcal{P}(\mathbb{N}^{\mathbb{N}})$ and $\mathrel{{}_{\mathrm{w}}}$ and
$\mathrel{{}_{\mathrm{s}}}$ define equivalence relations on
$\mathcal{P}(\mathbb{N}^{\mathbb{N}})$.

######  Definition I.4.12 (weak and strong degrees).

Suppose $P\subseteq\mathbb{N}^{\mathbb{N}}$. The _weak degree_ of $P$,
$\mathop{\deg_{\mathrm{w}}}(P)$, is the
$\mathrel{{}_{\mathrm{w}}}$-equivalence class containing $P$, and the _strong
degree_ of $P$, $\mathop{\deg_{\mathrm{s}}}(P)$, is the
$\mathrel{{}_{\mathrm{s}}}$-equivalence class containing $P$.

The set of all weak degrees is denoted by $\mathcal{D}_{\mathrm{w}}$, while
the set of all strong degrees is denoted by $\mathcal{D}_{\mathrm{s}}$.

Here we collect some simple facts about $\mathcal{D}_{\mathrm{w}}$ and
$\mathcal{D}_{\mathrm{s}}$ that we use repeatedly and often implicitly.

######  Proposition I.4.13.

(well-known) Let $P$ and $Q$ be mass problems and let $\mathcal{Q}$ a family
of mass problems.

  1. (a)

$P\mathrel{{}_{\mathrm{s}}}Q$ implies $P\mathrel{{}_{\mathrm{w}}}Q$.

  2. (b)

$Q\subseteq P$ implies $P\mathrel{{}_{\mathrm{s}}}Q$.

  3. (c)

$P\mathrel{{}_{\mathrm{w}}}P^{\mathrel{{}_{\mathrm{T}}}}$, where
$P^{\mathrel{{}_{\mathrm{T}}}}\mathrel{{\vdotdot}{\equal}}\\{Y\in\mathbb{N}^{\mathbb{N}}\mid\exists
X\in P\,(X\mathrel{{}_{\mathrm{T}}}Y)\\}$ is the _Turing upward closure_ of
$P$.

  4. (d)

$\inf\\{\mathop{\deg_{\mathrm{w}}}(P)\mid
P\in\mathcal{Q}\\}=\mathop{\deg_{\mathrm{w}}}\left(\tbigcup\slimits@\mathcal{Q}\right)$.

  5. (e)

$\sup\\{\mathop{\deg_{\mathrm{w}}}(P)\mid
P\in\mathcal{Q}\\}=\mathop{\deg_{\mathrm{w}}}\left(\tbigcap\slimits@\\{P^{\mathrel{{}_{\mathrm{T}}}}\mid
P\in\mathcal{Q}\\}\right)$.

  6. (f)

$\langle\mathcal{D}_{\mathrm{w}},\leq\rangle$ is a completely distributive
lattice.

  7. (g)

$\inf\\{\mathop{\deg_{\mathrm{s}}}(P),\mathop{\deg_{\mathrm{s}}}(Q)\\}=\mathop{\deg_{\mathrm{s}}}(P\times
Q)$, where $P\times Q\mathrel{{\vdotdot}{\equal}}\\{X\oplus Y\mid X\in P\wedge
Y\in Q\\}$.

  8. (h)

$\sup\\{\mathop{\deg_{\mathrm{s}}}(P),\mathop{\deg_{\mathrm{s}}}(Q)\\}=\mathop{\deg_{\mathrm{s}}}(\\{\langle
0\rangle X\mid X\in P\\}\cup\\{\langle 1\rangle Y\mid Y\in Q\\})$.

  9. (i)

$\mathrm{REC}\mathrel{{}_{\mathrm{s}}}P\mathrel{{}_{\mathrm{s}}}\emptyset$,
where $\mathrm{REC}=\\{X\in\mathbb{N}^{\mathbb{N}}\mid\text{$X$ is
recursive}\\}$.

  10. (j)

$\langle\mathcal{D}_{\mathrm{s}},\leq\rangle$ is a bounded distributive
lattice.

  11. (k)

For all $X,Y\in\mathbb{N}^{\mathbb{N}}$, $X\mathrel{{}_{\mathrm{T}}}Y$ if and
only if $\\{X\\}\mathrel{{}_{\mathrm{w}}}\\{Y\\}$, and if and only if
$\\{X\\}\mathrel{{}_{\mathrm{s}}}\\{Y\\}$. Consequently,
$\mathop{\deg_{\mathrm{T}}}(X)\mapsto\mathop{\deg_{\mathrm{w}}}(\\{X\\})$ and
$\mathop{\deg_{\mathrm{T}}}(X)\mapsto\mathop{\deg_{\mathrm{s}}}(\\{X\\})$
define embeddings of $\langle\mathcal{D}_{\mathrm{T}},\leq\rangle$ into
$\langle\mathcal{D}_{\mathrm{w}},\leq\rangle$ and
$\langle\mathcal{D}_{\mathrm{s}},\leq\rangle$, respectively.

  12. (l)

$P\mathrel{{}_{\mathrm{w}}}\mathrm{REC}$ if and only if
$P\cap\mathrm{REC}\neq\emptyset$.

Examples of mass problems, weak reductions, and strong reductions will be
encountered throughout the remainder of this thesis, though we give one
example presently which is neither empty nor weakly or strongly equivalent to
$\\{f\\}$ for some $f\in\mathbb{N}^{\mathbb{N}}$.

######  Example I.4.14.

Suppose $P\cap\mathrm{REC}=\emptyset$. Then
$P\subseteq\mathrm{REC}^{\mathsf{c}}$, so
$\mathrm{REC}^{\mathsf{c}}\mathrel{{}_{\mathrm{s}}}P$. It follows that
$\mathop{\deg_{\mathrm{w}}}(\mathrm{REC}^{\mathsf{c}})$ and
$\mathop{\deg_{\mathrm{s}}}(\mathrm{REC}^{\mathsf{c}})$ are immediate
successors of the minimum of $\mathcal{D}_{\mathrm{w}}$ and
$\mathcal{D}_{\mathrm{s}}$, respectively.

That $\mathrm{REC}^{\mathsf{c}}\mathrel{{}_{\mathrm{w}}}\\{X\\}$ (and
consequently $\mathrm{REC}^{\mathsf{c}}\mathrel{{}_{\mathrm{s}}}\\{X\\}$) for
any $X\in\mathbb{N}^{\mathbb{N}}$ follows from the fact that there exist
incomparable minimal nonrecursive Turing degrees.

####  I.4.3 $\mathcal{E}_{\mathrm{w}}$ and the Embedding Lemma

Particular attention is given to the weak degrees of nonempty $\Pi^{0}_{1}$
subsets of $\\{0,1\\}^{\mathbb{N}}$, which we call _$\Pi^{0}_{1}$ classes_,
serving a similar role in $\mathcal{D}_{\mathrm{w}}$ as the collection
$\mathcal{E}_{\mathrm{T}}$ of r.e. Turing degrees (i.e., Turing degrees of
r.e. sequences) in $\mathcal{D}_{\mathrm{T}}$.

######  Definition I.4.15.

$\mathcal{E}_{\mathrm{w}}\mathrel{{\vdotdot}{\equal}}\\{\mathop{\deg_{\mathrm{w}}}(P)\mid\text{$P\subseteq\\{0,1\\}^{\mathbb{N}}$
is $\Pi^{0}_{1}$}\\}$.

One motivation for $\mathcal{E}_{\mathrm{w}}$ in comparison to
$\mathcal{E}_{\mathrm{T}}$ is that specific, natural examples of weak degrees
in $\mathcal{E}_{\mathrm{w}}$ can be given while there are no known specific,
natural r.e. degrees aside from $\mathbf{0}$ and $\mathbf{0}^{\prime}$. See
[25] and [24] for additional details.

######  Proposition I.4.16.

Suppose $P\subseteq\\{0,1\\}^{\mathbb{N}}$ is given. The following are
equivalent.

  1. (a)

$P$ is $\Pi^{0}_{1}$.

  2. (b)

There exists a recursive tree $T\subseteq\\{0,1\\}$ such that $P$ is the set
of paths through $T$.

  3. (c)

There exists $e\in\mathbb{N}$ such that
$P=\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\varphi_{e}^{X}(0){\uparrow}\\}$.

Although our interests lie chiefly within $\mathcal{E}_{\mathrm{w}}$, the weak
degrees we consider are often most naturally represented by mass problems
which are not $\Pi^{0}_{1}$ subsets of $\\{0,1\\}^{\mathbb{N}}$. The following
result shows that this issue can be side-stepped as long as the mass problem
is sufficiently low in the arithmetical hierarchy.

######  Proposition I.4.17 (Embedding Lemma).

[27, Lemma 17.1] Suppose $P$ is a nonempty $\Pi^{0}_{1}$ subset of
$\\{0,1\\}^{\mathbb{N}}$ and $S$ is a $\Sigma^{0}_{3}$ subset of
$\mathbb{N}^{\mathbb{N}}$. Then there exists a nonempty $\Pi^{0}_{1}$ subset
$Q$ of $\\{0,1\\}^{\mathbb{N}}$ such that $Q\mathrel{{}_{\mathrm{w}}}P\cup S$.

One particular case which is especially well-behaved is with _recursively
bounded $\Pi^{0}_{1}$ classes_.

######  Definition I.4.18.

Suppose $h\colon\mathbb{N}\to(0,\infty)$ is a computable function. We write

$\displaystyle h^{n}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\sigma\in\mathbb{N}^{n}\mid\forall
i<n\,(\sigma(i)<h(i))\\},$ $\displaystyle h$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{\sigma\in\mathbb{N}\mid\forall
i<|\sigma|\,(\sigma(i)<h(i))\\}=\tbigcup\slimits@_{n\in\mathbb{N}}{h^{n}},$
$\displaystyle h^{\mathbb{N}}$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid\forall
i\,(X(i)<h(i))\\}.$

In other words, $h^{n}$ is the set of $h$-bounded strings of length $n$, $h$
is the set of all $h$-bounded strings, and $h^{\mathbb{N}}$ is the set of
$h$-bounded infinite sequences.

######  Lemma I.4.19.

The subspace topology on $h^{\mathbb{N}}\subseteq\mathbb{N}^{\mathbb{N}}$ has
a basis $\\{\left\llbracket\sigma\right\rrbracket_{h}\mid\sigma\in h\\}$,
where for $\sigma\in h$ we define

$\left\llbracket\sigma\right\rrbracket_{h}\mathrel{{\vdotdot}{\equal}}\\{X\in
h^{\mathbb{N}}\mid\sigma\subset X\\}.$

###### Proof.

For all $\sigma\in h$,
$h^{\mathbb{N}}\cap\left\llbracket\sigma\right\rrbracket=\left\llbracket\sigma\right\rrbracket_{h}$.
If $\sigma\in\mathbb{N}\setminus h$, then
$h^{\mathbb{N}}\cap\left\llbracket\sigma\right\rrbracket=\emptyset$. ∎

######  Proposition I.4.20.

(well-known) $h^{\mathbb{N}}$ is recursively homeomorphic to
$\\{0,1\\}^{\mathbb{N}}$.

###### Proof.

Define $\psi\colon h\to\\{0,1\\}$ recursively as follows:
$\psi(\langle\rangle)=\langle\rangle$ and given $\psi(\sigma)$ has been
defined, let $\psi(\sigma\langle
i\rangle)\mathrel{{\vdotdot}{\equal}}\psi(\sigma)\langle 1\rangle^{i}\langle
0\rangle$ for each $i<h(|\sigma|)-1$ and $\psi(\sigma\langle
h(|\sigma|)-1\rangle)\mathrel{{\vdotdot}{\equal}}\psi(\sigma)\langle
1\rangle^{h(|\sigma|)-1}$. We make the following observations:  (i) for all
$\sigma,\sigma^{\prime}\in h$, $\sigma\subseteq\sigma^{\prime}$ if and only if
$\psi(\sigma)\subseteq\psi(\sigma^{\prime})$, and  (ii) for all $\sigma\in h$,
$\left\llbracket\psi(\sigma)\right\rrbracket_{2}=\tbigcup\slimits@_{i<h(|\sigma|)}{\left\llbracket\psi(\sigma\langle
i\rangle)\right\rrbracket_{2}}$.

Now define $\Psi\colon h^{\mathbb{N}}\to\\{0,1\\}^{\mathbb{N}}$ by
$\Psi(X)\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@_{n\in\mathbb{N}}{\psi(X{\upharpoonright}\,n)}$.
Observation (i) above implies $\Psi$ is well-defined and injective, while
observation (ii) implies $\Psi$ is surjective. Given $\tau\in\\{0,1\\}$,
$\Psi^{-1}[\left\llbracket\tau\right\rrbracket_{2}]=\tbigcup\slimits@\\{\left\llbracket\sigma\right\rrbracket_{h}\mid\psi(\sigma)\supseteq\tau\\}$,
showing $\Psi$ is continuous. Conversely, given $\sigma\in h$,
$\Psi[\left\llbracket\sigma\right\rrbracket_{h}]=\left\llbracket\psi(\sigma)\right\rrbracket_{2}$
– that
$\Psi[\left\llbracket\sigma\right\rrbracket_{h}]\subseteq\left\llbracket\psi(\sigma)\right\rrbracket_{2}$
is immediate, while the reverse inclusion follows from observation (ii) above
– and hence $\Psi$ is an open map. Since $\Psi$ is clearly recursive, it is a
recursive homeomorphism. ∎

######  Definition I.4.21 (recursively bounded).

$P\subseteq\mathbb{N}^{\mathbb{N}}$ is _recursively bounded_ , or _r.b._ , if
there exists an recursive function $h\colon\mathbb{N}\to(1,\infty)$ such that
$P\subseteq h^{\mathbb{N}}$.

In particular, a _recursively bounded $\Pi^{0}_{1}$ class_, or a _r.b.
$\Pi^{0}_{1}$ class_, is a recursively bounded and $\Pi^{0}_{1}$ subset of
$\mathbb{N}^{\mathbb{N}}$.

######  Proposition I.4.22.

[24, Theorem4.7] Suppose $P$ is a r.b. $\Pi^{0}_{1}$ class and that
$\Psi\colon P\to\mathbb{N}^{\mathbb{N}}$ is a recursive functional.

  1. (a)

The image $\Psi[P]$ is recursively bounded and $\Pi^{0}_{1}$.

  2. (b)

$\Psi$ extends to a total recursive functional
$\tilde{\Psi}\colon\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}}$.

######  Corollary I.4.23.

Suppose $P$ is a r.b. $\Pi^{0}_{1}$ class. Then there exists a $\Pi^{0}_{1}$
subset $Q$ of $\\{0,1\\}^{\mathbb{N}}$ which is recursively homeomorphic to
$P$.

###### Proof.

Let $\Psi$ be the recursive homeomorphism defined in the proof of Proposition
I.4.20. Then Proposition I.4.22(a) shows that the image $Q$ of $P$ under
$\Psi$ is another $\Pi^{0}_{1}$ class. ∎

##  Chapter II Complexity, Avoidance, and Depth

In Chapter I we gave brief definitions of $\mathrm{COMPLEX}(f)$ and
$\mathrm{DNR}(p)$ for $f$ an order function and $p$ a nondecreasing computable
function, as well as alluded to a variation on $\mathrm{DNR}$ which we termed
$\mathrm{LU\kern-0.50003ptA}$.

In Section II.1, we define Martin-Löf randomness through three paradigms as a
precursor to their generalizations which give rise to $f$-randomness and
strong $f$-randomness for any computable function
$f\colon\\{0,1\\}\to\mathbb{R}$, with Martin-Löf randomness corresponding to
$(\lambda\sigma.|\sigma|)$-randomness. The classes $\mathrm{COMPLEX}(f)$ are
defined and shown to lie in $\mathcal{E}_{\mathrm{w}}$. Finally, we list some
of the properties of prefix-free and conditional prefix-free complexity that
we will use later.

In Section II.2, we show that the effect of the growth rate of $p$ on
$\mathop{\deg_{\mathrm{w}}}\mathrm{DNR}(p)$ depends explicitly on the choice
of admissible enumeration used, and motivate the definition of the class
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$ for any computable
$p\colon\mathbb{N}\to(1,\infty)$ and partial recursive $\psi$. Linearly
universal partial recursive functions are defined, followed by defining
$\mathrm{LU\kern-0.50003ptA}(p)$ as the union of the classes
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$ as $\psi$ ranges over those linearly
universal partial recursive functions. Basic and technical results are covered
for the linearly universal partial recursive functions,
$\mathrm{LU\kern-0.50003ptA}(p)$, and
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$ more generally.

In Section II.3, we formally define the notion of being fast-growing and slow-
growing for an order function and address the problem “Given a recursive
sequence of fast-growing (resp., slow-growing) order functions $\langle
p_{k}\rangle_{k\in\mathbb{N}}$, find fast-growing (resp., slow-growing) order
functions $q^{+}$ and $q^{-}$ such that
$p_{k}\mathrel{{}_{\mathrm{dom}}}q^{+}$ and
$q^{-}\mathrel{{}_{\mathrm{dom}}}p_{k}$ for all $k\in\mathbb{N}$.” Towards
that end, for the slow-growing case we prove that such a $q^{-}$ always exists
and that a $q^{+}$ exists with additional hypotheses on $\langle
p_{k}\rangle_{k\in\mathbb{N}}$ (Proposition II.3.2), but that a $q^{+}$ need
not exist in general (Example II.3.3). On the other hand, for the fast-growing
case we can prove that $q^{+}$ always exists and that $q^{-}$ exists with
additional hypotheses on the $p_{k}$’s and the sequence $\langle
p_{k}\rangle_{k\in\mathbb{N}}$ (Proposition II.3.5).

To better understand the extra hypothesis of requiring
$\tsum\slimits@_{n=0}{p(n)^{-1}}$ not only be finite but also recursive, we
prove the following equivalence:

######  Proposition II.3.10.

Suppose $p\colon\mathbb{N}\to(0,\infty)$ is a fast-growing order function and
let $\overline{p}\colon[0,\infty)\to(0,\infty)$ be any continuous
nonincreasing extension of $p$. Then $\tsum\slimits@_{n=0}{p(n)^{-1}}$ is a
recursive real if and only if $\int_{0}{\overline{p}(x)^{-1}\,\mathrm{d}x}$ is
a recursive real.

Section II.4 introduces the notion of depth for r.b. $\Pi^{0}_{1}$ classes, of
which our interest is based on strong general properties of deep r.b.
$\Pi^{0}_{1}$ classes and the fact that the classes
$\mathrm{LU\kern-0.50003ptA}_{p}$ are deep exactly when $p$ is slow-growing.
Depth is shown to be well-behaved with respect to $\mathrel{{}_{\mathrm{s}}}$
while slightly less well-behaved for $\mathrel{{}_{\mathrm{w}}}$. We end the
section with a discussion of the applicability of ‘depth’ to subsets of
$\mathbb{N}^{\mathbb{N}}$ which are not r.b. $\Pi^{0}_{1}$ classes.

###  II.1 Algorithmic Randomness and Complexity

Downey & Hirschfeldt identify three paradigms through which one can attempt to
make precise the idea of ‘algorithmic randomness’ or ‘algorithmic complexity’.
[6, Chapter 6]

The measure-theoretic paradigm:

If $X\in\\{0,1\\}^{\mathbb{N}}$ is ‘random’, then it should pass all
‘statistical tests’ (e.g., $X$ should obey the Law of Large Numbers, the Law
of the Iterated Logarithm, etc.). Any ‘statistical test’ should be such that
the set of sequences failing that statistical test should be ‘effectively
null’ (so $X$ should not fall into any effectively null subset of
$\\{0,1\\}^{\mathbb{N}}$).

The computational paradigm:

If $X\in\\{0,1\\}^{\mathbb{N}}$ is ‘random’, then the initial segments of $X$
should be ‘maximally difficult’ to describe, in the sense that we should need
to know roughly $n$ bits of information in order to describe
$X{\upharpoonright}\,n$.

The unpredictability paradigm:

If $X\in\\{0,1\\}^{\mathbb{N}}$ is ‘random’ and we imagine that each bit of
$X$ represents the result of a coin flip whose outcome we are betting on, then
there shouldn’t be any strategy by which we make arbitrarily high earnings.

There are several ways to make precise the notion of randomness from any of
these three paradigms (some of them inequivalent), and our interest will not
solely be on ‘randomness’ but on notions of ‘partial randomness’. Quantifying
‘how random’ a partially random sequence is yields the complexity hierarchy.

####  II.1.1 Martin-Löf Randomness

Martin-Löf randomness is among the most standard ways to capture the notion of
a sequence being algorithmically random, and our definitions of partial
randomness will be generalizations of those for Martin-Löf randomness.

The first definition we give comes from the within the measure-theoretic
paradigm.

######  Definition II.1.1 (Martin-Löf randomness).

A _Martin-Löf test_ , or _ML test_ , is a sequence $\langle
U_{i}\rangle_{i\in\mathbb{N}}$ of uniformly $\Sigma^{0}_{1}$ subsets of
$\\{0,1\\}^{\mathbb{N}}$ such that $\lambda(U_{i})\leq 2^{-i}$ for each
$i\in\mathbb{N}$. Such an ML test _covers_ $X\in\\{0,1\\}^{\mathbb{N}}$ if
$X\in\tbigcap\slimits@_{i\in\mathbb{N}}{U_{i}}$. $X\in\\{0,1\\}^{\mathbb{N}}$
is _Martin-Löf random_ (or _$1$ -random_) if no ML test covers $X$. The set of
all Martin-Löf random sequences is denoted by $\mathsf{MLR}$.

The computational paradigm involves measuring the ‘complexity’ of initial
segments of an $X\in\\{0,1\\}^{\mathbb{N}}$. There are two relevant notions of
complexity, that of _prefix-free complexity_ and _a priori complexity_.

First, prefix-free complexity:

######  Definition II.1.2 (prefix-free machine).

A _machine_ is a partial recursive function $M\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\\{0,1\\}\to\\{0,1\\}$. A machine $M$ is _prefix-free_ if
$\operatorname{dom}M$ is prefix-free. A prefix-free machine $U$ is said to be
_universal_ if whenever $M$ is another prefix-free machine there is a
$\rho\in\\{0,1\\}$ such that $U(\rho\tau)\simeq M(\tau)$ for all
$\tau\in\\{0,1\\}$.

######  Lemma II.1.3.

[6, Proposition 3.5.1.(ii)] There exists a universal prefix-free machine.

######  Definition II.1.4 (prefix-free complexity).

Fix a universal prefix-free machine $U$. Given $\sigma\in\\{0,1\\}$, its
_prefix-free complexity_ (with respect to $U$) is defined by

$\operatorname{KP}(\sigma)=\operatorname{KP}_{U}(\sigma)\mathrel{{\vdotdot}{\equal}}\min\\{|\tau|\mid
U(\tau){\downarrow}=\sigma\\}.$

The second notion of complexity we use is that of a priori complexity, which
has a more pronounced measure-theoretic leaning than that of prefix-free
complexity:

######  Definition II.1.5 (continuous semimeasure).

A _continuous semimeasure_ is a function $\nu\colon\\{0,1\\}\to[0,1]$ such
that $\nu(\langle\rangle)=1$ and $\nu(\sigma)\geq\nu(\sigma\langle
0\rangle)+\nu(\sigma\langle 1\rangle)$ for all $\sigma\in\\{0,1\\}$. A
continuous semimeasure $\nu$ is _left recursively enumerable_ , or _left r.e._
, if it is left r.e. in the usual sense. A left r.e. continuous semimeasure
$\mathbf{M}$ is _universal_ if whenever $\nu$ is another left r.e. continuous
semimeasure there is a $c\in\mathbb{N}$ such that $\nu(\sigma)\leq
c\cdot\mathbf{M}(\sigma)$ for all $\sigma\in\\{0,1\\}$.

######  Lemma II.1.6.

[6, Theorem 3.16.2] There exists a universal left r.e. continuous semimeasure.

######  Definition II.1.7 (a priori complexity).

Fix a universal left r.e. continuous semimeasure $\mathbf{M}$. Given
$\sigma\in\\{0,1\\}$, its _a priori complexity_ (with respect to $\mathbf{M}$)
is defined by

$\operatorname{KA}(\sigma)=\operatorname{KA}_{\mathbf{M}}(\sigma)\mathrel{{\vdotdot}{\equal}}-\log_{2}\mathbf{M}(\sigma).$

The complexity of an $X\in\\{0,1\\}^{\mathbb{N}}$ can be quantified by the
growth rate of the complexities of its initial segments.

######  Definition II.1.8 ((strong) $1$-complexity).

$X\in\\{0,1\\}^{\mathbb{N}}$ is _$1$ -complex_ if there exists
$c\in\mathbb{N}$ such that $\operatorname{KP}(X{\upharpoonright}\,n)\geq n-c$
for all $n\in\mathbb{N}$, and is _strongly $1$-complex_ if there exists
$c\in\mathbb{N}$ such that $\operatorname{KA}(X{\upharpoonright}\,n)\geq n-c$
for all $n\in\mathbb{N}$.

The predictability paradigm includes supermartingales as one way to capture a
notion of betting.

######  Definition II.1.9 (supermartingale and success).

A _supermartingale_ is a function $d\colon\\{0,1\\}\to[0,\infty)$ such that
$2d(\sigma)\geq d(\sigma\langle 0\rangle)+d(\sigma\langle 1\rangle)$ for all
$\sigma\in\\{0,1\\}$. A supermartingale $d$ is _left recursively enumerable_ ,
or _left r.e._ , if it left r.e. in the usual sense. A left r.e.
supermartingale $d$ _succeeds on $X\in\\{0,1\\}^{\mathbb{N}}$_ if
$\limsup_{n}{d(X{\upharpoonright}\,n)}=\infty$.

Each of these approaches (among several others) ultimately give the same
notion of an $X\in\\{0,1\\}^{\mathbb{N}}$ being ‘algorithmically random’.

######  Proposition II.1.10.

[6, Chapter 6] Suppose $X\in\\{0,1\\}^{\mathbb{N}}$. The following are
equivalent.

  1. (i)

$X$ is Martin-Löf random.

  2. (ii)

$X$ is $1$-complex.

  3. (iii)

$X$ is strongly $1$-complex.

  4. (iv)

No left r.e. supermartingale succeeds on $X$.

####  II.1.2 Partial Randomness

Even if $X\notin\mathsf{MLR}$, $X$ may still exhibit some degree of
randomness. _Partial_ randomness can be approached from the measure-theoretic,
computational, and predictability paradigms just as in the case of Martin-Löf
randomness, though the resulting definitions need not be equivalent in
general. Notions of ‘partial $f$-randomness’ can be motivated by interpreting
Martin-Löf randomness as corresponding to the choice
$f(\sigma)\mathrel{{\vdotdot}{\equal}}|\sigma|$ for $\sigma\in\\{0,1\\}$.

######  Notation II.1.11.

Unless otherwise specified, $f$ denotes a computable function
$f\colon\\{0,1\\}\to\mathbb{R}$.

Concerning the measure-theoretic paradigm, the map $\sigma\mapsto
2^{-f(\sigma)}$ no longer induces a pre-measure on the algebra of basic open
subsets of $\\{0,1\\}^{\mathbb{N}}$; given a $\Sigma^{0}_{1}$ subset
$U\subseteq\\{0,1\\}^{\mathbb{N}}$, it matters how $U$ is expressed as a union
of basic open sets. For this reason, our emphasis is on r.e. subsets of
$\\{0,1\\}$ instead of $\Sigma^{0}_{1}$ subsets of $\\{0,1\\}^{\mathbb{N}}$.
Moreover, we consider two distinct ways to capture the idea of the
‘$f$-weight’ of a subset of $\\{0,1\\}$.

######  Definition II.1.12 (direct and prefix-free $f$-weight).

The _direct $f$-weight_ of a set of strings $S\subseteq\\{0,1\\}$ is defined
by

$\operatorname{dwt}_{f}(S)\mathrel{{\vdotdot}{\equal}}\tsum\slimits@_{\sigma\in
S}{2^{-f(\sigma)}}.$

Its _prefix-free $f$-weight_ is defined by

$\operatorname{pwt}_{f}(S)\mathrel{{\vdotdot}{\equal}}\sup\\{\operatorname{dwt}_{f}(A)\mid\text{prefix-
free $A\subseteq S$}\\}.$

######  Definition II.1.13 ((strong) $f$-randomness).

Suppose $\langle S_{i}\rangle_{i\in\mathbb{N}}$ is a sequence of uniformly
r.e. subsets of $\\{0,1\\}$. $\langle S_{i}\rangle_{i\in\mathbb{N}}$ is a _$f$
-ML test_ if $\operatorname{dwt}_{f}(S_{i})\leq 2^{-i}$ for each
$i\in\mathbb{N}$ and a _weak $f$-ML test_ if
$\operatorname{pwt}_{f}(S_{i})\leq 2^{-i}$ for each $i\in\mathbb{N}$. $\langle
S_{i}\rangle_{i\in\mathbb{N}}$ _covers_ $X\in\\{0,1\\}^{\mathbb{N}}$ if
$X\in\tbigcap\slimits@_{i\in\mathbb{N}}{\left\llbracket
S_{i}\right\rrbracket}$. $X\in\\{0,1\\}^{\mathbb{N}}$ is _$f$ -random_ if no
$f$-ML test covers $X$ and _strongly $f$-random_ if no weak $f$-ML test covers
$X$.

Replacing the map $\sigma\mapsto|\sigma|$ with $f$ quickly generalizes the
notion of $1$-complexity and strong $1$-complexity:

######  Definition II.1.14 ((strong) $f$-complexity).

$X\in\\{0,1\\}^{\mathbb{N}}$ is _$f$ -complex_ if there exists
$c\in\mathbb{N}$ such that $\operatorname{KP}(X{\upharpoonright}\,n)\geq
f(X{\upharpoonright}\,n)-c$ for all $n\in\mathbb{N}$, and is _strongly
$f$-complex_ if there exists $c\in\mathbb{N}$ such that
$\operatorname{KA}(X{\upharpoonright}\,n)\geq f(X{\upharpoonright}\,n)-c$ for
all $n\in\mathbb{N}$.

For supermartingales and success, we generalize the notion of success.

######  Definition II.1.15 ($f$-success).

A left r.e. supermartingale $d$ _$f$ -succeeds on
$X\in\\{0,1\\}^{\mathbb{N}}$_ if

$\limsup_{n}{\left(d(X{\upharpoonright}\,n)\cdot
2^{n-f(X{\upharpoonright}\,n)}\right)}=\infty.$

Unlike when $f(\sigma)\mathrel{{\vdotdot}{\equal}}|\sigma|$, these notions are
no longer all necessarily equivalent, instead forming two groups. In summary:

######  Proposition II.1.16.

[10, Theorem 2.6, Theorem 2.8] [13, Theorem 4.1.6, Theorem 4.1.8, Theorem
4.2.3] Suppose $X\in\\{0,1\\}^{\mathbb{N}}$ and
$f\colon\\{0,1\\}\to\mathbb{R}$ is computable.

  1. (a)

$X$ is $f$-random if and only if it is $f$-complex.

  2. (b)

$X$ is strongly $f$-random if and only if it is strongly $f$-complex, and if
and only if no left r.e. supermartingale $f$-succeeds on $X$.

######  Remark II.1.17.

In [13], Hudelson generalizes the supermartingale approach to partial
randomness by modifying the definition of a supermartingale, defining a _left
r.e. $f$-supermartingale_ to be a left r.e. function
$d\colon\\{0,1\\}\to[0,\infty)$ such that

$2^{-f(\sigma)}\cdot d(\sigma)\geq 2^{-f(\sigma\langle 0\rangle)}\cdot
d(\sigma\langle 0\rangle)+2^{-f(\sigma\langle 1\rangle)}\cdot d(\sigma\langle
1\rangle)$

for all $\sigma\in\\{0,1\\}$, with $d$ _succeeding on
$X\in\\{0,1\\}^{\mathbb{N}}$_ if
$\limsup_{n}{d(X{\upharpoonright}\,n)}=\infty$. For every
$X\in\\{0,1\\}^{\mathbb{N}}$, there exists an $f$-supermartingale $d$
succeeding on $X$ if and only if there exists a supermartingale $\tilde{d}$
$f$-succeeding on $X$.

Our choice to use ordinary supermartingales and $f$-success follows the
approaches used for $f$ of the form
$f(\sigma)\mathrel{{\vdotdot}{\equal}}\delta\cdot|\sigma|$ for
$\delta\in(0,1]$ in [5] and [9].

Although $f$-randomness does not in general imply strong $f$-randomness (see,
e.g., [13, Theorem 4.3.2]), if $g$ grows sufficiently faster than $f$, then
$g$-randomness will imply strong $f$-randomness:

######  Proposition II.1.18.

[10, Theorem 3.5] Suppose $f,g\colon\\{0,1\\}\to\mathbb{R}$ are computable
functions and $X\in\\{0,1\\}^{\mathbb{N}}$ is $g$-random. If there exists a
nondecreasing $h\colon\mathbb{R}\to\mathbb{R}$ such that
$\tsum\slimits@_{n=1}{2^{-h(n)}}<\infty$ and for which $g(\sigma)\geq
f(\sigma)+h(f(\sigma))$ for all $\sigma\in\\{0,1\\}$, then $X$ is strongly
$f$-random.

######  Corollary II.1.19.

[10, Theorem 3.6] Suppose $k>0$ and $\varepsilon>0$, and let
$g=f+\log_{2}f+\log_{2}\log_{2}f+\@cdots+\log_{2}^{k-1}f+(1+\varepsilon)\log_{2}^{k}f$.
Then any $g$-random $X\in\\{0,1\\}^{\mathbb{N}}$ is strongly $f$-random.

####  II.1.3 Randomness and Complexity as Mass Problems

For each computable $f\colon\\{0,1\\}\to\mathbb{R}$ there is an associated
mass problem consisting of all $X\in\\{0,1\\}^{\mathbb{N}}$ which are
$f$-complex (equivalently, $f$-random). We use the following notation:

######  Definition II.1.20.

Suppose $f\colon\\{0,1\\}\to\mathbb{R}$ is computable and $c\in\mathbb{N}$.
Then

$\displaystyle\mathrm{COMPLEX}(f,c)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\forall
n\,(\operatorname{KP}(X{\upharpoonright}\,n)\geq
f(X{\upharpoonright}\,n)-c)\\},$ $\displaystyle\mathrm{COMPLEX}(f)$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\\{X\in\\{0,1\\}^{\mathbb{N}}\mid\text{$X$
is $f$-complex}\\}=\tbigcup\slimits@_{c=0}{\mathrm{COMPLEX}(f,c)}.$

######  Notation II.1.21.

Given $\delta\in(0,1]$, define $f\colon\\{0,1\\}\to\mathbb{R}$ by
$f(\sigma)\mathrel{{\vdotdot}{\equal}}\delta|\sigma|$. We write
$\mathrm{COMPLEX}(\delta,c)$ for $\mathrm{COMPLEX}(f,c)$ and
$\mathrm{COMPLEX}(\delta)$ for $\mathrm{COMPLEX}(f)$.

######  Proposition II.1.22.

The sets $\mathrm{COMPLEX}(f,c)$ are $\Pi^{0}_{1}$, uniform in $c$. Thus,
$\mathrm{COMPLEX}_{f}$ is $\Sigma^{0}_{2}$ and consequently
$\mathop{\deg_{\mathrm{w}}}(\mathrm{COMPLEX}(f))\in\mathcal{E}_{\mathrm{w}}$
whenever $\mathrm{COMPLEX}(f)\neq\emptyset$.

###### Proof.

Suppose $X\in\\{0,1\\}^{\mathbb{N}}$ and $c\in\mathbb{N}$. Fix a universal
prefix-free machine $U$ and let $e$ be such that $U(\tau)\simeq\sigma$ if and
only if
$\varphi_{e}(\operatorname{str}^{-1}(\tau))\simeq\operatorname{str}^{-1}(\sigma)$.
Then

$X\in\mathrm{COMPLEX}(f,c)\iff\forall n\forall
s\forall\tau\,(\varphi_{e,s}(\operatorname{str}^{-1}(\tau)){\downarrow}=\operatorname{str}^{-1}(X{\upharpoonright}\,n)\to|\tau|\geq
f(X{\upharpoonright}\,n)-c).$

The uniformity of the above predicate shows that $\mathrm{COMPLEX}(f)$ is
$\Sigma^{0}_{2}$.

If $\mathrm{COMPLEX}(f)\neq\emptyset$, then
$\mathrm{COMPLEX}(f,c)\neq\emptyset$ for some $c\in\mathbb{N}$. In particular,
$\mathrm{COMPLEX}(f)$ contains a nonempty $\Pi^{0}_{1}$ subset of
$\\{0,1\\}^{\mathbb{N}}$. Thus, the  (Embedding Lemma). implies
$\mathop{\deg_{\mathrm{w}}}(\mathrm{COMPLEX}(f))\in\mathcal{E}_{\mathrm{w}}$.
∎

Often $f(\sigma)$ depends only on $|\sigma|$; such $f$ are said to be _length-
invariant_ and correspond exactly with computable functions of the form
$\mathbb{N}\to\mathbb{R}$. We extend our notation for $\mathrm{COMPLEX}(f)$ to
such functions.

######  Notation II.1.23.

If $f\colon\mathbb{N}\to\mathbb{R}$ is a computable function and
$c\in\mathbb{N}$, then $\mathrm{COMPLEX}(f,c)$ stands for
$\mathrm{COMPLEX}(\tilde{f},c)$, where $\tilde{f}\colon\\{0,1\\}\to\mathbb{R}$
is defined by $\tilde{f}(\sigma)\mathrel{{\vdotdot}{\equal}}f(|\sigma|)$ for
$\sigma\in\\{0,1\\}$.

Because we are often interested in _partial_ randomness and in light of
Theorem II.4.12, we often only consider $f$ satisfying the following
condition:

######  Definition II.1.24 (sub-identical).

A function $f\colon\\{0,1\\}\to[0,\infty)$ is _sub-identical_ if
$\lim_{n\to\infty}{(n-f(X{\upharpoonright}\,n))}=\infty$ for every
$X\in\\{0,1\\}^{\mathbb{N}}$.

Likewise, a function $f\colon\mathbb{N}\to[0,\infty)$ is _sub-identical_ if
$\lim_{n\to\infty}{(n-f(n))}=\infty$.

Thanks to the presence of $c$ in the definition
$\mathrm{COMPLEX}(f)=\tbigcup\slimits@_{c\in\mathbb{N}}{\mathrm{COMPLEX}(f,c)}$,
if $f(n)=g(n)$ for almost all $n$, then
$\mathrm{COMPLEX}_{f}=\mathrm{COMPLEX}_{g}$.

######  Convention II.1.25.

Given $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{R}$, suppose $f{\upharpoonright}\,\mathbb{N}_{\geq
a}$ is a total, computable, nondecreasing, unbounded function for some
$a\in\mathbb{N}$. Define $\tilde{f}\colon\mathbb{N}\to\mathbb{R}$ by
$\tilde{f}(n)\mathrel{{\vdotdot}{\equal}}f(n)$ for $n\geq a$ and
$\tilde{f}(n)\mathrel{{\vdotdot}{\equal}}f(a)$ otherwise. Then $\tilde{f}$ is
an order function, and we let $\mathrm{COMPLEX}(f)$ denote the class
$\mathrm{COMPLEX}(\tilde{f})$. This allows us to make sense of something like,
e.g., $\mathrm{COMPLEX}(\log_{2})$.

####  II.1.4 Properties of Prefix-Free Complexity

Here we collect some of the results concerning prefix-free complexity we make
use of later. Several of these results involve _conditional_ prefix-free
complexity.

######  Definition II.1.26 (oracle prefix-free machine).

An _oracle prefix-free machine_ is a partial recursive function
$M\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\\{0,1\\}\times\\{0,1\\}\to\\{0,1\\}$ such that  (i) if
$M^{\tau}(\sigma){\downarrow}$ and $\tau\subseteq\tau^{\prime}$, then
$M^{\tau^{\prime}}(\sigma){\downarrow}=M^{\tau}(\sigma)$ and  (ii)
$\\{\sigma\mid\langle\sigma,\tau\rangle\in\operatorname{dom}M\\}$is prefix-
free for every $\tau\in\\{0,1\\}$.  An oracle prefix-free machine $U$ is
_universal_ if for every oracle prefix-free machine $M$ there exists
$\rho\in\\{0,1\\}$ such that $U^{\tau}(\rho\sigma)\simeq M^{\tau}(\sigma)$ for
all $\sigma\in\\{0,1\\}$.

######  Lemma II.1.27.

[6, Section 3.2] There exists a universal oracle prefix-free machine $U$.

######  Definition II.1.28 (conditional prefix-free complexity).

[6, Section 3.2] Fix a universal oracle prefix-free machine $U$. Given
$\sigma,\tau\in\\{0,1\\}$, the _conditional prefix-free complexity of $\sigma$
given $\tau$_ (with respect to $U$) is defined by

$\operatorname{KP}(\sigma\mid\tau)=\operatorname{KP}_{U}(\sigma\mid\tau)\mathrel{{\vdotdot}{\equal}}\min\\{|\rho|\mid
U^{\overline{\tau}}(\rho){\downarrow}=\sigma\\},$

where
$\overline{\tau}=\langle\tau(0),\tau(0),\tau(1),\tau(1),\ldots,\tau(|\tau|-1),\tau(|\tau|-1),0,1\rangle$.

######  Notation II.1.29.

Temporarily write
$\vec{\sigma}\mathrel{{\vdotdot}{\equal}}\operatorname{str}\bigl{(}\pi^{(k)}(\operatorname{str}^{-1}(\sigma_{1}),\operatorname{str}^{-1}(\sigma_{2}),\ldots,\operatorname{str}^{-1}(\sigma_{k}))\bigr{)}$
for $\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\in\\{0,1\\}$. Then given
$\sigma_{1},\sigma_{2},\ldots,\sigma_{k},\tau_{1},\tau_{2},\ldots,\tau_{m}\in\\{0,1\\}$,
we define

$\displaystyle\operatorname{KP}(\sigma_{1},\sigma_{2},\ldots,\sigma_{k})$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\operatorname{KP}(\vec{\sigma}),$
$\displaystyle\operatorname{KP}(\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\mid\tau_{1},\tau_{2},\ldots,\tau_{m})$
$\displaystyle\mathrel{{\vdotdot}{\equal}}\operatorname{KP}(\vec{\sigma}\mid\vec{\tau}).$

######  Notation II.1.30.

Given functions $f,g\colon S\to\mathbb{R}$, we write $f{}^{+}g$ to mean that
there exists $c\in\mathbb{N}$ such that $f(x)\leq g(x)+c$ for all $x\in S$. We
write $f=^{+}g$ if $f{}^{+}g$ and $g{}^{+}f$. By an abuse of notation, we may
write $f(x){}^{+}g(x)$ or $f(x)=^{+}g(x)$ where $x$ is an indeterminate to
indicate that $f{}^{+}g$ or $f=^{+}g$, respectively.

######  Proposition II.1.31.

  1. (a)

[6, Theorem 3.6.1 & Corollary 3.6.2] Kraft-Chaitin: Suppose
$(d_{i},\tau_{i})_{i\in\mathbb{N}}$ is a recursive sequence of pairs
$(d_{i},\tau_{i})\in\mathbb{N}\times\\{0,1\\}$ such that
$\tsum\slimits@_{i=0}{2^{-d_{i}}}\leq 1$. Then there exists a prefix-free
machine $M$ and strings $\sigma_{i}$ such that $|\sigma_{i}|=d_{i}$ and
$M(\sigma_{i})=\tau_{i}$ for all $i\in\mathbb{N}$ and
$\operatorname{dom}M=\\{\sigma_{i}\mid i\in\mathbb{N}\\}$. Consequently,
$\operatorname{KP}(\tau_{i}){}^{+}d_{i}$.

  2. (b)

[6, Proposition 3.5.4] If $f\colon\\{0,1\\}\to\\{0,1\\}$ is computable, then
$\operatorname{KP}(f(\sigma)){}^{+}\operatorname{KP}(\sigma)$ for all
$\sigma\in\\{0,1\\}$.

  3. (c)

[6, Corollary 3.7.5] For any $k$ and $\varepsilon>0$,
$\operatorname{KP}(\sigma){}^{+}|\sigma|+\log|\sigma|+\log\log|\sigma|+\@cdots+(1+\varepsilon)\log^{k}|\sigma|$.

  4. (d)

[6, Proposition 3.7.13] For all $\sigma,\tau\in\\{0,1\\}$,
$\operatorname{KP}(\sigma\tau)\leq\operatorname{KP}(\sigma,\tau){}^{+}\operatorname{KP}(\sigma)+\operatorname{KP}(\tau)$.

  5. (e)

[6, Theorem 3.10.2]
$\operatorname{KP}(\sigma,\tau)=^{+}\operatorname{KP}(\sigma)+\operatorname{KP}(\tau\mid\sigma,\operatorname{KP}(\sigma))=^{+}\operatorname{KP}(\sigma)+\operatorname{KP}(\tau\mid\sigma)$,
where $\sigma$ is the lexicographically least $\tau$ such that
$U(\tau){\downarrow}=\sigma$ in $s$ stages for the least possible $s$.

######  Corollary II.1.32.

Suppose $f\colon(\\{0,1\\})^{k}\to\\{0,1\\}$ is computable. Then for all
$\sigma_{1},\sigma_{2},\ldots,\sigma_{k}$,

$\operatorname{KP}(f(\sigma_{1},\sigma_{2},\ldots,\sigma_{k})){}^{+}\operatorname{KP}(\sigma_{1})+\operatorname{KP}(\sigma_{2})+\@cdots+\operatorname{KP}(\sigma_{k}).$

###  II.2 $\mathrm{DNR}$ and Avoidance

The diagonally non-recursive (or $\mathrm{DNR}$) hierarchy consists of the
sets $\mathrm{DNR}(p)$ for $p\colon\mathbb{N}\to(1,\infty)$ computable, where
‘diagonally non-recursive’ is with respect to a fixed admissible enumeration
$\varphi$.

######  Definition II.2.1 (diagonally non-recursive).

The set of _diagonally non-recursive_ sequences,
$\mathrm{DNR}\subseteq\mathbb{N}^{\mathbb{N}}$, is defined by
$\mathrm{DNR}\mathrel{{\vdotdot}{\equal}}\\{f\in\mathbb{N}^{\mathbb{N}}\mid\forall
n\,(f(n)\nsimeq\varphi_{n}(n))\\}$. Additionally, given a recursive
$p\colon\mathbb{N}\to(1,\infty)$, we define:

$\mathrm{DNR}(p)\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid
X\in\mathrm{DNR}\wedge\forall n\,(X(n)<p(n))\\}.$

The weak degree of $\mathrm{DNR}(p)$ has a dependence on the growth rate of
$p$. At one extreme,
$\mathbf{1}\mathrel{{\vdotdot}{\equal}}\mathop{\deg_{\mathrm{w}}}(\mathrm{DNR}(2))$
is the maximum weak degree in $\mathcal{E}_{\mathrm{w}}$ [27, Theorem 14.6].
As the growth rate of $p$ rises the weak degree of $\mathrm{DNR}(p)$ falls;
[17, Theorem 2.3] shows that the class
$\mathrm{DNR}_{\mathrm{rec}}\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@\\{\mathrm{DNR}(p)\mid\text{$p$
recursive}\\}$ is weakly equivalent to the class
$\mathrm{COMPLEX}\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@\\{\mathrm{COMPLEX}(f)\mid\text{$f$
recursive}\\}$. Several results (e.g., [9], [15]) show that for certain
properties of interest, every element of $\mathrm{DNR}(p)$ computes an
infinite sequence with that desired property if $p$ is sufficiently slow-
growing.

If we wish to replace ‘sufficiently slow-growing’ with explicit bounds, we
quickly run into problems – the weak degree of $\mathrm{DNR}(p)$ depends not
only on $p$, but also on the particular admissible enumeration $\varphi$ used
in the definition of $\mathrm{DNR}(p)$, a fact that has been observed in [24,
Remark 10.6], [2, §7.3], and [19]. In particular, we can show:

######  Proposition II.2.2.

There exist admissible enumerations $\varphi$ and $\tilde{\varphi}$ such that
the weak degree of $\mathrm{DNR}(\lambda n.n)$ differs when defined with
respect to $\varphi$ and $\tilde{\varphi}$.

###### Proof.

[2] shows that there exist admissible enumerations $\varphi$ for which
$\mathrm{DNR}(p)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathsf{MLR}$ (where
$\mathrm{DNR}(p)$ is defined with respect to that particular choice of
enumeration $\varphi$) if and only if
$\tsum\slimits@_{n=0}{p(n)^{-1}}=\infty$.111This fact has also been
independently observed by Greenberg, Miller [19], and Slaman. Let $\varphi$ be
such an admissible enumeration.

We define a new admissible enumeration $\tilde{\varphi}$. Given
$x\in\mathbb{N}$, define

$\tilde{\varphi}_{e}(x)\simeq\begin{cases}\varphi_{n}(x)&\text{if
$e=2^{n}$,}\\\ {\uparrow}&\text{otherwise.}\end{cases}$

It is straight-forward to check that $\tilde{\varphi}$ is an admissible
enumeration.

Write $\mathrm{DNR}^{(1)}$ to mean $\mathrm{DNR}$ with respect to the
enumeration $\varphi$ and $\mathrm{DNR}^{(2)}$ to mean $\mathrm{DNR}$ with
respect to the enumeration $\tilde{\varphi}$. Our assumption about $\varphi$
implies $\mathrm{DNR}^{(1)}(\lambda
n.n)\mathrel{\mathrel{{}_{\mathrm{w}}}}\mathsf{MLR}$ while
$\mathrm{DNR}^{(1)}(\lambda n.2^{n})\mathrel{{}_{\mathrm{w}}}\mathsf{MLR}$.
However, $\mathrm{DNR}^{(2)}(\lambda
n.n)\mathrel{{}_{\mathrm{s}}}\mathrm{DNR}^{(1)}(\lambda n.2^{n})$ and hence
$\mathrm{DNR}^{(2)}(\lambda n.n)\mathrel{{}_{\mathrm{w}}}\mathsf{MLR}$ and so
$\mathrm{DNR}^{(1)}(\lambda n.n)$ and $\mathrm{DNR}^{(2)}(\lambda n.n)$ are
not weakly equivalent. ∎

With this dependence in mind, if we wish to discuss the weak degrees of the
classes $\mathrm{DNR}_{p}$, then the notation ‘$\mathrm{DNR}$’ should be
replaced with one explicitly acknowledging the choice of admissible
enumeration implicit in ‘$\mathrm{DNR}$’. By definition $X\in\mathrm{DNR}$ if
and only if $X$ avoids the diagonal $\psi(e)\simeq\varphi_{e}(e)$, i.e.,
$X\cap\psi=\emptyset$. In particular, a more precise observation is that
$\mathrm{DNR}$ depends only on the choice of $\psi$, where $\psi$ is chosen
among the diagonals of admissible enumerations. The constraint that $\psi$ be
the diagonal of an admissible enumeration can be lifted to give a more general
notion.

######  Definition II.2.3 (avoidance).

Suppose $\psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ is a partial recursive function. The class
$\mathrm{A\kern-0.80002ptvoid}^{\psi}$ is defined by
$\mathrm{A\kern-0.80002ptvoid}^{\psi}\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid
X\cap\psi=\emptyset\\}$. Additionally, given any recursive
$p\colon\mathbb{N}\to(1,\infty)$, we define:

$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)\mathrel{{\vdotdot}{\equal}}\\{X\in\mathbb{N}^{\mathbb{N}}\mid
X\cap\psi=\emptyset\wedge\forall n\,(X(n)<p(n))\\}.$

In this more general framework, the analogs of the diagonals of admissible
enumerations are the universal partial recursive funcitons.

######  Definition II.2.4 (universal partial recursive function).

A partial recursive function $\psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ is _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 is a total recursive function $f$ such
that $\psi\circ f=\theta$.

This is based on the fact that the diagonal of any admissible enumeration
$\varphi$ is universal.

######  Proposition II.2.5.

The diagonal of any admissible enumeration is universal.

###### Proof.

Let $\varphi$ be an admissible enumeration and $\psi$ its diagonal, and let
$\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ be any partial recursive function. Let
$\chi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{3}\to\mathbb{N}$ be defined by
$\chi(e,x,y)\simeq\varphi_{e}(x)$ for $e,x,y\in\mathbb{N}$. By the
Parametrization Theorem, there exists a total recursive function
$g\colon\mathbb{N}^{2}\to\mathbb{N}$ such that
$\varphi_{g(e,x)}(y)\simeq\chi(e,x,y)\simeq\varphi_{e}(x)$ for all
$e,x,y\in\mathbb{N}$. Let $e\in\mathbb{N}$ satisfy
$\varphi_{e}(x)\simeq\theta(x)$ for all $x\in\mathbb{N}$, and let
$f\colon\mathbb{N}\to\mathbb{N}$ be defined by
$f(x)\mathrel{{\vdotdot}{\equal}}g(e,x)$. Then

$(\psi\circ
f)(x)\simeq\varphi_{g(e,x)}(g(e,x))\simeq\varphi_{e}(x)\simeq\theta(x).$

As $\theta$ was arbitrary, it follows that $\psi$ is universal. ∎

####  II.2.1 Linearly Universal Avoidance

As with $\mathrm{DNR}(p)$, $\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$ still
depends on the choice of universal partial recursive function $\psi$. To
remove the dependence on a _single_ choice of universal partial recursive
function we instead choose a _collection_ of universal partial recursive
functions.

######  Definition II.2.6.

Suppose $\mathcal{C}$ is a collection of partial recursive functions and
$p\colon\mathbb{N}\to(1,\infty)$ is recursive. We define

$\mathrm{A\kern-0.80002ptvoid}^{\mathcal{C}}(p)\mathrel{{\vdotdot}{\equal}}\tbigcup\slimits@_{\psi\in\mathcal{C}}{\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)}.$

The choice of $\mathcal{C}$ we make follows the convention introduced by [29],
motivated by [2] and [19].

######  Definition II.2.7 (linearly universal partial recursive function).

A _linearly universal partial recursive function_ is a partial recursive
function $\psi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ such that for any partial recursive
$\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ there exist $a,b\in\mathbb{N}$ such that
$\psi(ax+b)\simeq\theta(x)$ for all $x\in\mathbb{N}$.

######  Definition II.2.8.

Given a recursive $p\colon\mathbb{N}\to(1,\infty)$ we define
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{\vdotdot}{\equal}}\mathrm{A\kern-0.80002ptvoid}^{\mathcal{LU}}(p)$,
where $\mathcal{LU}$ is the family of linearly universal partial recursive
functions.

######  Remark II.2.9.

The approach used in [2] and [19] is to use
$\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$, where $\psi$ is the diagonal of a
‘linear enumeration’, i.e., an admissible enumeration $\varphi$ for which
there is a total recursive $\ell\colon\mathbb{N}^{2}\to\mathbb{N}$ satisfying
the following conditions:  (i) For all $e,x\in\mathbb{N}$,
$\psi(\ell(e,x))\simeq\varphi_{e}(x)$ and  (ii) for each $e\in\mathbb{N}$
there exist $a,b\in\mathbb{N}$ such that $\ell(e,x)\leq ax+b$ for all
$x\in\mathbb{N}$.

####  II.2.2 Properties of Linearly Universal Partial Recursive Functions

Every linearly universal partial recursive function $\psi$ produces an
effective enumeration $\varphi$ of the partial recursive functions by setting

$\varphi_{e}(x)\simeq\psi((e)_{0}x+(e)_{1})$

for $e,x\in\mathbb{N}$, where
$(-)_{i}\mathrel{{\vdotdot}{\equal}}\pi_{i}\circ(\pi^{(2)})^{-1}$ for
$i\in\\{0,1\\}$ (so $\pi^{(2)}((n)_{0},(n)_{1})=n$ for all $n\in\mathbb{N}$).
This enumeration $\varphi$ is admissible.

######  Proposition II.2.10 (Parametrization Theorem for Linearly Universal
Partial Recursive Functions).

Suppose $\psi$ is a linearly universal partial recursive function and
$\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{k+1}\to\mathbb{N}$ is a partial recursive function. There
exist elementary recursive functions $A,B\colon\mathbb{N}^{k}\to\mathbb{N}$
such that

$\psi(A(\mathbf{x})y+B(\mathbf{x}))\simeq\theta(\mathbf{x},y)$

for all $\mathbf{x}\in\mathbb{N}^{k}$ and $y\in\mathbb{N}$.

###### Proof.

Because $\psi$ is linearly universal, there exists $a,b\in\mathbb{N}$ such
that $\psi(a\pi^{(k+1)}(\mathbf{x},y)+b)\simeq\theta(\mathbf{x},y)$ for all
$\mathbf{x}\in\mathbb{N}^{k}$ and $y\in\mathbb{N}$. Thus, defining
$A,B\colon\mathbb{N}^{k}\to\mathbb{N}$ by

$A(\mathbf{x})\mathrel{{\vdotdot}{\equal}}a2^{\pi^{(k)}(\mathbf{x})+1}\quad\text{and}\quad
B(\mathbf{x})\mathrel{{\vdotdot}{\equal}}a(2^{\pi^{(k)}(\mathbf{x})}-1)+b$

gives

$\displaystyle\psi(A(\mathbf{x})y+B(\mathbf{x}))$
$\displaystyle\simeq\psi(a2^{\pi^{(k)}(\mathbf{x})+1}y+a(2^{\pi^{(k)}(\mathbf{x})}-1)+b)$
$\displaystyle\simeq\psi(a(2^{\pi^{(k)}(\mathbf{x})}(2y+1)-1)+b)$
$\displaystyle\simeq\psi(a\pi^{(k+1)}(\mathbf{x},y)+b)$
$\displaystyle\simeq\theta(\mathbf{x},y)$

for all $\mathbf{x}\in\mathbb{N}^{k}$ and $y\in\mathbb{N}$. ∎

######  Corollary II.2.11.

Suppose $\psi$ is a linearly universal partial recursive function. Then the
effective enumeration $\varphi$ defined by
$\varphi_{e}(n)\mathrel{{\vdotdot}{\equal}}\psi((e)_{0}n+(e)_{1})$ is
admissible.

######  Corollary II.2.12 (Recursion Theorem for Linearly Universal Partial
Recursive Functions).

Suppose $\psi$ is a linearly universal partial recursive function and
$\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{k+2}\to\mathbb{N}$ is a partial recursive function. Then
there exist $a,b\in\mathbb{N}$ such that

$\psi(a\pi^{(k)}(\mathbf{x})+b)\simeq\theta(a,b,\mathbf{x})$

for all $\mathbf{x}\in\mathbb{N}^{k}$.

###### Proof.

Let $\tilde{\theta}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}^{k+1}\to\mathbb{N}$ be defined by

$\tilde{\theta}(c,\mathbf{x})\simeq\theta((c)_{0},(c)_{1},\mathbf{x})$

for all $c\in\mathbb{N}$ and $\mathbf{x}\in\mathbb{N}^{k}$. Corollaries
II.2.11, LABEL: and I.3.12 show that that there exists an $e\in\mathbb{N}$
such that

$\psi((e)_{0}\pi^{(k)}(\mathbf{x})+(e)_{1})\simeq\varphi_{e}^{(k)}(\mathbf{x})\simeq\tilde{\theta}(e,\mathbf{x})\simeq\theta((e)_{0},(e)_{1},\mathbf{x})$

for all $\mathbf{x}\in\mathbb{N}$. Thus, we may let $a=(e)_{0}$ and
$b=(e)_{1}$. ∎

Moreover, the diagonal of $\varphi$ is linearly universal.

######  Proposition II.2.13.

If $\psi_{0}$ is a linearly universal partial recursive function, then the
partial function $\psi$ defined by $\psi(e)\simeq\psi_{0}((e)_{0}e+(e)_{1})$
for $e\in\mathbb{N}$ is also linearly universal partial recursive.

###### Proof.

Suppose $\theta\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{N}$ is a partial recursive function. There are $a$
and $b$ such that $\forall x\,(\psi_{0}(ax+b)\simeq\theta(x))$. For any
$x\in\mathbb{N}$, $\pi^{(2)}(0,x)=2^{0}(2x+1)-1=2x$, so

$\psi(2x)\simeq\psi(\pi^{(2)}(0,x))\simeq\psi_{0}(0\cdot x+x)=\psi_{0}(x).$

It follows that $\psi$ is linearly universal. ∎

Together, Corollary II.2.11 and Proposition II.2.13 allow us to enjoy the
benefits of linearly universal partial recursive functions and of admissible
enumerations simultaneously, e.g., having access to the particularly nice
versions of the Parametrization and Recursion Theorems in the forms of
Propositions II.2.10, LABEL: and II.2.12, respectively.

Another convenient property of linearly universal partial recursive functions
is that we may we edit any finite number of values without affecting the
linear universality.

######  Proposition II.2.14.

Suppose $\psi,\chi$ are partial recursive functions such that
$\psi(n)\simeq\chi(n)$ for almost all $n\in\mathbb{N}$. Then $\psi$ is
linearly universal if and only if $\chi$ is linearly universal.

###### Proof.

Suppose $\psi$ is linearly universal. Let $N\in\mathbb{N}$ be such that
$\psi(x)\simeq\chi(x)$ for all $x\geq N$. Consider the 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}$ defined by

$\theta(x)\simeq\begin{cases}\psi(x-N)&\text{if $x\geq N$,}\\\
{\uparrow}&\text{otherwise.}\end{cases}$

Because $\psi$ is linearly universal, there are $a,b\in\mathbb{N}$ such that
$\psi(ax+b)\simeq\theta(x)$ for all $x\in\mathbb{N}$. $\theta$ is nonconstant,
so $a\neq 0$ and hence $ax+b\geq x$ for all $x\in\mathbb{N}$. Thus, for all
$x\in\mathbb{N}$,

$\chi(ax+(aN+b))\simeq\psi(ax+(aN+b))\simeq\psi(a(x+N)+b)\simeq\theta(x+N)\simeq\psi(x),$

showing $\chi$ is linearly universal. ∎

######  Convention II.2.15.

Given $p\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:{\subseteq}\\!}\mskip 6.0mu plus
1.0mu\mathbb{N}\to\mathbb{R}$, suppose $p{\upharpoonright}\,\mathbb{N}_{\geq
a}$ is a total, computable, nondecreasing, unbounded function with image in
$(1,\infty)$ for some $a\in\mathbb{N}$. Define
$\tilde{p}\colon\mathbb{N}\to(1,\infty)$ by
$\tilde{p}(x)\mathrel{{\vdotdot}{\equal}}p(x)$ for $x\geq a$ and
$\tilde{p}(x)\mathrel{{\vdotdot}{\equal}}p(a)$ otherwise. Then $\tilde{p}$ is
an order function, and we let $\mathrm{LU\kern-0.50003ptA}(p)$ denote the
class $\mathrm{LU\kern-0.50003ptA}(\tilde{p})$. This allows us to make sense
of something like, e.g., $\mathrm{LU\kern-0.50003ptA}(\log_{2})$.

#####  II.2.2.1 Basic Properties of the $\mathrm{LU\kern-0.50003ptA}$
Hierarchy

The regularity of the manner in which linearly universal partial recursive
functions express their universality allows us to prove some simple but useful
strong and weak reductions.

######  Proposition II.2.16.

Let $p,q\colon\mathbb{N}\to(1,\infty)$ be recursive functions.

  1. (a)

If $q(x)=p(ax+b)$ for some $a\in\mathbb{N}_{>0}$ and $b\in\mathbb{N}$ for all
$x\in\mathbb{N}$, then
$\mathrm{LU\kern-0.50003ptA}(p)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.

  2. (b)

If $X\in\mathrm{LU\kern-0.50003ptA}(p)$, $Y\in p^{\mathbb{N}}$, and
$X(x)=Y(x)$ for almost all $x\in\mathbb{N}$, then
$Y\in\mathrm{LU\kern-0.50003ptA}(p)$.

  3. (c)

If $p\mathrel{{}_{\mathrm{dom}}}q$, then
$\mathrm{LU\kern-0.50003ptA}(q)\mathrel{{}_{\mathrm{s}}}\mathrm{LU\kern-0.50003ptA}(p)$.

  4. (d)

If for all $a,b\in\mathbb{N}$ we have $q(ax+b)\leq p(x)$ for almost all
$x\in\mathbb{N}$ and $\psi_{0}$ is a partial recursive function, then
$\mathrm{A\kern-0.80002ptvoid}^{\psi_{0}}(p)\mathrel{{}_{\mathrm{w}}}\mathrm{LU\kern-0.50003ptA}(q)$.

###### Proof.

  1. (a)

Let $\psi$ be a linearly universal partial recursive function. If
$X\in\mathrm{A\kern-0.80002ptvoid}^{\psi}(p)$, then
$X\in\mathrm{A\kern-0.80002ptvoid}^{\psi}(q)\subseteq\mathrm{LU\kern-0.50003ptA}(q)$