# A total Solovay reducibility and totalizing of the notion of speedability

Wolfgang Merkle and Ivan Titov

(March 2021)

###### Abstract

While the set of Martin-Löf random left-c.e. reals is equal to the maximum
degree of Solovay reducibility, Miyabe, Nies and Stephan [6] have shown that
the left-c.e. Schnorr random reals are not closed upwards under Solovay
reducibility. Recall that for two left-c.e. reals $\alpha$ and $\beta$, the
former is Solovay reducible to the latter in case there is a partially
computable function $\varphi$ and constant $c$ such that for all rational
numbers $q<\beta$ we have

$\alpha-\varphi(q)<c(\beta-q).$

By requiring the translation function $\varphi$ to be total, we introduce a
total version of Solovay reducibility that implies Schnorr reducibility.
Accordingly, by Downey and Griffiths [2], the set of Schnorr random left-c.e.
reals is closed upwards relative to total Solovay reducibility.

Furthermore, we observe that the notion of speedability introduced by Merkle
and Titov [4] can be equivalently characterized via partial computable
translation functions in a way that resembles Solovay reducibility. By
requiring the translation function to be total, we obtain the concept of total
speedability. Like for speedability, this notion does not depend on the choice
of the speeding constant.

##  1 A total version of Solovay reducibility

We first review the usual definition of Solovay reducibility as a reducibility
via a partially computable rational-valued function. For any unexplained
notions, see Downey and Hirschfeldt [3].

######  Definition 1.1 (Solovay [7], 1975).

Let $\alpha$ and $\beta$ be reals and let $c>0$ be a rational number. Then
$\alpha$ is Solovay reducible to $\beta$ with respect to a constant $c$,
written $\alpha\leq_{S,c}\beta$, if there is a partial computable function
$\varphi\colon\mathbb{Q}\rightarrow\mathbb{Q}$ such that for all $q<\beta$ it
holds that $\varphi(q)\downarrow<\alpha$ and $\alpha-\varphi(q)<c(\beta-q)$.
The real $\alpha$ is Solovay reducible to $\beta$, written
$\alpha\leq_{S}\beta$, if $\alpha$ is Solovay reducible to $\beta$ with
respect to some $c$.

In case $\alpha\leq_{S}\beta$, we will also say that $\alpha$ is $S$-reducible
to $\beta$, and similar notation will be used for other reducibilities
introduced in what follows.

######  Definition 1.2 (total Solovay reducibility, $\leq^{tot}_{S,c}$).

A real $\alpha$ is total Solovay reducible to a real $\beta$ with respect to a
constant $c$, written $\alpha\leq^{tot}_{S,c}\beta$, if there is a computable
function $f\colon\mathbb{Q}\rightarrow\mathbb{Q}$ such that for all $q<\beta$
it holds that $f(q)<\alpha$ and $\alpha-f(q)<c(\beta-q)$. The real $\alpha$ is
total Solovay reducible to $\beta$, written $\alpha\leq_{S}^{tot}\beta$, if
$\alpha$ is total Solovay reducible to $\beta$ with respect to some $c$.

The total Solovay reducibility obviously implies the normal one, thus, the
Martin-Löf random left-c.e. reals are closed upwards relative to the total
Solovay reducibility. One can proof that, in general case, the total Solovay
reducibility implies the $\leq_{S}^{1a}$-reducibility defined by Zheng and
Rettinger in [8].

##  2 The structural properties of the total Solovay degrees on the left-c.e.
reals

In this section, we argue that total Solovay reducibility is in
$\Sigma^{0}_{3}$ but is not a standard reducibility in the sense of Downey and
Hirschfeldt [3] because neither is addition a join operator nor is there a
least degree.

######  Proposition 2.1.

Total Solovay reducibility is in $\Sigma^{0}_{3}$.

###### Proof.

Let $\alpha^{0},\alpha^{1},...$ be an effective enumeration of left-c.e.
reals, where we can assume that, for given $n$, on can compute a recursive
index for a nondecreasing approximation $a_{0}^{n},a_{1}^{n},\ldots$ to
$\alpha^{n}$ from below. Then we have

$\displaystyle\alpha^{a}\leq_{S}^{tot}\alpha^{b}\iff$
$\displaystyle\exists\langle e,c\rangle\forall\langle q,s\rangle\exists\langle
r,t\rangle\colon$
$\displaystyle\bigg{(}\varphi_{e}(q)[t]\downarrow\wedge(q<b_{s}\implies\big{(}a_{r}-\varphi_{e}(q)>0\wedge
a_{r}-\varphi_{e}(q)<c(b_{s}-q)\big{)}\bigg{)}.$

∎

######  Proposition 2.2.

Let $\alpha$ be a left-c.e. real, and let $r>0$ be a rational number. Then it
holds that $r\alpha\equiv_{S}^{tot}\alpha$.

###### Proof.

It holds that $r\alpha\leq_{S}^{tot}\alpha$ via the identify function and
constant $r$, and similarly for a reduction in the reverse direction with
constant $1/r$. ∎

Next we review the notion of a hyperimmune set.

######  Definition 2.3.

Let $A$ be an infinite set. By $p_{A}$, we denote the principal function of
$A$, i.e., the members of $A$ are $p_{A}(0)<p_{A}(1)<\cdots$. Let $k_{A}(n)$
be the least member of $A\setminus\\{0,\ldots,n-1\\}$.

Recall that a set $A$ is hyperimmune if $p_{A}$ is not majorized by a
computable function, i.e., for no computable function $g$ we have
$p_{A}(n)\leq g(n)$ for all $n$.

######  Lemma 2.4.

For any set $A$, the following assertions are equivalent:

  * (i)

$p_{A}$ is not majorized by any computable function,

  * (ii)

$k_{A}$ is not majorized by any computable function.

###### Proof.

If the computable function $g(n)$ majorizes $k_{A}(n)$, where we can assume
that $h$ in nondecreasing, then the desired computable function that majorizes
$p_{A}(n)$ is given by

$n\mapsto\underbrace{g(g(...(g(0))...))}_{\text{$n$-fold application
of\leavevmode\nobreak\ $g$}}.$

Conversely, in case the computable function $g(n)$ majorizes $p_{A}(n)$, then
the function $n\mapsto g(n+1)$ majorizes $k_{A}(n)$. ∎

######  Proposition 2.5.

There exists no least degree in the total Solovay degrees.

Every least set with respect to total Solovay reducibility is also a least set
with respect to Solovay reducibility. Since the sets of the latter type are
exactly the computable sets, the proposition is immediate from the following
lemma.

######  Lemma 2.6.

Let $\alpha=0.A(0)\ldots$ and $\beta=0.B(0)\ldots$ be reals where the set $A$
is computable and infinite. Then $\alpha$ is total Solovay reducible to
$\beta$ if and only if the set $B$ is not hyperimmune.

###### Proof.

First assume that $B$ is not hyperimmune. For a dyadic rational $q$ that can
be written as $q=0.\sigma$ where the last letter of $\sigma$ is equal to $1$,
define $|q|=|\sigma|$. Then, for any such $q$ and $\sigma$ where $q<\beta$, we
have

$2^{-k_{B}(|q|)}\leq\beta-0.\sigma=\beta-q.$

By Lemma 2.4, we can fix a computable function $g$ that majorizes $k_{B}$. We
obtain a computable function $f$ witnessing $\alpha\leq_{S}^{tot}\beta$ by
choosing $f(q)<\alpha$ such that we have

$\alpha-f(q)<2^{-g(|q|)}.$

Next assume that $\alpha$ is total Solovay reducible to $\beta$ via some
function $f$ and constant $c$. Then, for every $n$ and for $q_{n}=0.B(0)\ldots
B(n-1)$, we have $q<\beta$, thus, for some appropriate constant $d$, one holds
that

$g(n):=\min_{|\sigma_{n}|=n}\\{{\alpha-f(0.\sigma_{n}):\alpha-f(0.\sigma_{n})>0}\\}\leq\alpha-f(q)<c(\beta-q)\leq
2^{-k_{B}(n)+d}.$

Consequently, the function $n\mapsto d+\lceil\log g(n)\rceil$ is a computable
upper bound for $k_{B}$, hence $B$ is not hyperimmune. ∎

Indeed, the total Solovay degree structure satisfies the following stronger
property, which we state here without proof.

######  Proposition 2.7.

There exists a countably infinite antichain of mutually
$\leq_{S}^{tot}$-incomparable left-c.e. reals such that each of them is
incomparable with every computable real.

Before proving that addition is not a join operator and not even an upper
bound operator for total Solovay reducibility, we introduce the uniform
version of the Schnorr reducibility introduced by Downey and Griffiths [2] in
2004. The possibility to define the uniform Schnorr reducibility has been
noticed by Downey, Hirschfeldt [3, footnote to Definition 9.17.1] in 2010.

######  Definition 2.8 (Downey and Griffiths [2]; Downey and Hirschfeldt [3]).

A real $\alpha$ is uniformly Schnorr reducible, or $uSch$-reducible, to a real
$\beta$ with respect to a constant $c$, written $\alpha\leq_{uSch,c}\beta$, if
there is a computable functional $\varphi$ that, given a description of a
computable measure machine (or, shortly, cmm) $B$, returns a description of
another cmm $\varphi(B)$, so that

$K_{\varphi(B)}(\alpha\upharpoonright n)\leq K_{B}(\beta\upharpoonright
n)+c\quad\text{for all }n.$

The real $\alpha$ is uniform Schnorr reducible to $\beta$, written
$\alpha\leq_{uSch}\beta$, if $\alpha$ is uniform Schnorr reducible to $\beta$
with respect to some $c$.

Obviously, the uniform Schnorr reducibility implies the Schnorr reducibility,
with respect to which the Schnorr random reals are closed upwards.

######  Proposition 2.9.

For all left-c.e. $\alpha$ and $\beta$, $\alpha\leq_{S}^{tot}\beta$ implies
$\alpha\leq_{uSch}\beta$.

######  Corollary 2.10.

The Schnorr random left-c.e. reals are closed upwards under total Solovay
reducibility.

###### Proof.

Let $f$ be a total computable function, such that
$\alpha\leq^{tot}_{S,c}\beta$ via $f$. Given a cmm machine $B$ computing
$\beta$, we construct a cmm machine $A$ computing $\alpha$ in the following
uniform way:

Input: $(x\in\mathbb{Q},w\in\\{0,1\\}^{\lceil log(c)+1\rceil})$.

  * •

Compute $\sigma:=B(x)$ (the computation halts iff $x\in dom(B)$).

  * •

Compute $\tau$ so that $0.\tau:=(f(0.\sigma)\upharpoonright n)$.

If $0.\sigma<\beta$, then on holds

$\alpha-f(0.\sigma)<c(\beta-0.\sigma).$

In particular, if $0.\sigma=\beta\upharpoonright n$, then
$\beta-0.\sigma<2^{-n}$, so $\alpha-f(0.\sigma)<c2^{-n}=2^{\lceil
log(c)\rceil-n}$.

Thus,

$\alpha\upharpoonright
n-0.\tau<\alpha-f(0.\sigma)+f(0.\sigma)-(f(0.\sigma)\upharpoonright
n)<c2^{-n}+2^{-n}=2^{\lceil log(c+1)\rceil-n}.$

  * •

return $y\in\\{0,1\\}^{n}$, so that $0.y=0.\tau+2^{-n}\cdot 0.w$

The constructed machine $A$ has the following properties:

  * •

prefix-freeness since $B$ is prefix-free),

  * •

computable measure of the domain since the property

$B(x)\downarrow\implies A\big{(}(x,w)\big{)}\downarrow\forall
w\in\\{0,1\\}^{\lceil log(c+1)\rceil}$

implies, that $\mu\big{(}dom(A)\big{)}=\mu\big{(}dom(B)\big{)}$,

  * •

the inequality $K_{A}(\alpha\upharpoonright n)\leq K_{B}(\beta\upharpoonright
n)+log(c+1)+O(1)$ for all $n$ since there always exists a word
$w\in\\{0,1\\}^{\lceil log(c+1)\rceil}$ such that

$\alpha\upharpoonright n-0.\tau=2^{-n}\cdot 0.w,$

hence, for that $w$, on holds $A(x,w)=y$, such that

$0.y=0.\tau+2^{-n}\cdot 0,w=\alpha\upharpoonright n,$

that implies $K_{A}(\alpha\upharpoonright n)\leq|x|+|w|$, where $x$ may be the
shortest code of $\beta\upharpoonright n$.

∎

######  Remark.

The uniform Schnorr reducibility is, due to the similar argumentation, also
implied by the weaken version of the total Solovay reducibility, whose
requirement for $f$ differs from the original one in the additional term:

$\alpha-f(q)<c(\beta-q)+2^{-|q|}.$

The motivation of this weakening is that now its lattice on the field of
left-c.e. reals has a minimal degree containing all the computable reals.

######  Proposition 2.11.

There is a pair of left-c.e.reals $\alpha,\beta$ where
$\alpha\nleq_{S}^{tot}\alpha+\beta$.

###### Proof.

Miyabe, Nies and Stephan [6, Paragraph 3] demonstrated that there exists a
pair of left-c.e. reals $\alpha$ and $\beta$ such that
$\alpha\nleq_{Sch}\alpha+\beta$. Thus we also have
$\alpha\nleq_{S}^{tot}\alpha+\beta$ because total Solovay reducibility implies
Schnorr reducibility. ∎

##  3 Speedability as a self-reducibility

On the let of left-c.e. reals, the notion of speedability has been introduced
by Merkle and Titov [4] in 2020 as a self-reducibility via respect to the
constant $1$

######  Definition 3.1 (Merkle and Titov [4]).

A function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ is a speed-up function if
it is nondecreasing and $n\leq f(n)$ holds for all $n$. A left-c.e. number
$\alpha$ is $\rho$-speedable with respect to its given left approximation
$a_{0},a_{1},\ldots\nearrow\alpha$ for some real number $\rho\in[0,1)$ if
there is a computable speed-up function $f$ such that we have

$\liminf\limits_{n\to\infty}\frac{\alpha-a_{f(n)}}{\alpha-a_{n}}\leq\rho,$ (1)

and speedable if it is $\rho$-speedable with respect to some its left-c.e.
approximation for some $\rho\in(0,1)$. Otherwise we call $\alpha$
nonspeedable.

Whether a real is speedable depends neither on the left-c.e. approximation nor
on the constant $\rho$ one considers.

######  Theorem 3.2 (Merkle and Titov [4]).

Every speedable left-c.e. real number is $\rho$-speedable for any ${\rho>0}$
with respect to any of its left approximations.

The following theorem is immediate from the main result of Barmpalias and
Lewis-Pye [1].

######  Theorem 3.3 (Barmpalias and Lewis-Pye [1]).

Martin-Löf random left-c.e. real numbers are never speedable.

By the following proposition, the notion of speedability can be equivalently
characterized as a Solovay reduction of a real number to itself via a special
partial computable functions on the rational numbers. By applying the same
characterization to computable functions, in what follows we obtain a variant
of speedability, similar to the introduction of total Solovay reducibility.

######  Proposition 3.4 (Functional characterization of speedability).

Let $\alpha$ be a left-c.e. real and let $\rho$ be a real number such that
$0<\rho<1$. Then $\alpha$ is speedable if and only if there is a partial
computable function $g\colon\mathbb{Q}\rightarrow\mathbb{Q}$ that is defined
and nondecreasing on the interval $(-\infty,\alpha)$, maps this interval to
itself and satisfies

$\liminf\limits_{q\nearrow\alpha}\frac{\alpha-g(q)}{\alpha-q}\leq\rho.$ (2)

######  Remark.

Note that the characteristic of speedability given in Proposition 3.4 does not
require the existence of a left-c.e. approximation of the real $\alpha$, thus,
can be considered as an extension of the speedability notion on all (i.e. not
only left-c.e.) reals.

###### Proof.

Fix some left approximation $a_{0},a_{1},\ldots$ of $\alpha$. First, assume
that $\alpha$ is speedable. By Theorem 3.2 there is then a computable speed-up
function $f$ that witnesses that $\alpha$ is $\rho$-speedable with respect to
its left approximation $a_{0},a_{1},\ldots$ . Let $g$ be the partial
computable function on the set of rational numbers that maps every $q<\alpha$
to the least index $i$ such that $q\leq a_{i}$ and is undefined for all other
$q$. Here we assume that rational numbers are represented in a form such that
equality is a computable predicate. Then the partial function $g$ defined by

$g(q)=a_{f(n(q))},$

by choice of $n$ and $f$, is partial computable, is defined and nondecreasing
on the interval $(-\infty,\alpha)$, and maps this interval to itself.
Furthermore, the sequence $a_{0},a_{1},\ldots$ witnesses that (2) holds
because we have $g(a_{i})=a_{f(i)}$.

Next assume that there is a function $g$ as stated in the proposition. Then
there is a not necessarily computable left approximation $q_{0},q_{1},\ldots$
of $\alpha$ such that we have

$\liminf\limits_{j\rightarrow\infty}\frac{\alpha-g(q_{j})}{\alpha-
q_{j}}\leq\rho.$

Let $f$ be the computable speed up function that maps $i$ to the least index
$n>i$ such that $g(a_{i+1})<a_{n}$. Then, for all $q$ and $i$ such that $q$ is
an element of the half-open interval $[a_{i},a_{i+1})$, we have

$\frac{\alpha-a_{f(i)}}{\alpha-
a_{i}}\leq\frac{\alpha-g(a_{i+1})}{\alpha-q}\leq\frac{\alpha-g(q)}{\alpha-q}.$

In particular, this chain of inequalities holds true with $q$ replaced by any
of the $q_{j}$, which, by choice of the $q_{j}$, implies that $\alpha$ is
$\rho$-speedable via its left approximation $a_{0},a_{1},\ldots$ and the
speed-up function $f$. ∎

From Proposition 3.4 it is immediate that the equivalent characterization of
speedability stated here does not depend on the choice of $\rho$ in the
interval $(0,1)$. In particular, the characterization holds for some $\rho$ in
this interval if and only if it holds for all $\rho$ in this interval.

In a same way as the totalizing of translation function for the Solovay
reducibility, we can totalize the concept of speedability by requiring the
function $g$ from the latter definition to be total.

######  Definition 3.5.

Let $\rho$ be a real number such that $0<\rho<1$. A left-c.e. real $\alpha$ is
called total $\rho$-speedable if there exists a nondecreasing computable
function $g\colon\mathbb{Q}\mapsto\mathbb{Q}$ that maps every $q$ in the
interval $(-\infty,\alpha)$ to a value $g(q)>q$ in this interval and satisfies

$\liminf\limits_{q\nearrow\alpha}\frac{\alpha-g(q)}{\alpha-q}\leq\rho.$ (3)

Such a function $g$ is called total speed-up function.

By the following proposition, the total version of speedability does again not
depend on the choice of the constant. The proof is omitted due to space
considerations.

######  Proposition 3.6.

Whether a left-c.e. real is total $\rho$-speedable does not depend on the
choice of $\rho\in(0,1)$.

Barmpalias and Lewis-Pye [1] have shown that speedability implies Martin-Löf
nonrandomness. We currently research the characteristics of the total speed-up
function via which the total speedability will imply Schnorr nonrandomness.

## References

  * [1] George Barmpalias and Andrew Lewis-Pye. Differences of halting probabilities. _Journal of Computer and System Sciences_ 89:349–360 (2017).
  * [2] Rodney Downey and Evan Griffiths. Schnorr randomness. _Journal of Symbolic Logic_ 69(2):533–554 (2004).
  * [3] Rodney Downey and Denis Hirschfeldt. _Algorithmic Randomness and Complexity_ , Springer, Berlin (2010).
  * [4] Wolfgang Merkle and Ivan Titov. Speedable left-c.e. numbers. _CSR 2020: Computer Science –- Theory and Applications_ pp 303–313 (2020).
  * [5] Joseph Miller. On work of Barmpalias and Lewis-Pye: A derivation on the d.c.e. reals. _Lecture Notes in Computer Science_ 10010:644–-659 (2016).
  * [6] Kenshi Miyabe, André Nies, and Frank Stephan. Randomness and Solovay degrees. _Journal of Logic and Analysis_ 10(3):1–13 (2018).
  * [7] Robert Solovay. Draft of paper (or series of papers) on Chaitin’s work. _Unpublished notes_ , 215 pages (1975)
  * [8] Xizhong Zheng and Robert Rettinger. On the Extensions of Solovay-Reducibility. _COCOON 2004: Computing and Combinatorics_ pp 360–369 (2004).