# Relative Randomness and Continuous Translation Functions

Ivan Titov

► To cite this version:

Ivan Titov. Relative Randomness and Continuous Translation Functions. 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), Aug 2025, Varsovie, Poland. pp.91, 10.4230/LIPIcs.MFCS.2025.91 . hal-05250942

HAL Id: hal-05250942

https://hal.science/hal-05250942v1

Submitted on 12 Sep 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Relative randomness and continuous translation functions

Ivan Titov

<figure><img src="image_2.png" /></figure>

Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France

## Abstract

The notions of Martin-Löf randomness and of Solovay reducibility, as well as their relations to each other, are central objects of study in algorithmic randomness. When restricted to left-c.e. reals, Solovay reducibility of $α$ to $β$ can be characterized [16] as the existence of two left approximations $a_0, a_1, ...$ and $b_0, b_1, ...$ of $α$ and $β$, respectively, such that the ratios $\frac{α-a_n}{β-b_n}$ are bounded from above. By a celebrated result of Kučera and Slaman, among left-c.e. reals the Martin-Löf random ones are largest with respect to Solovay reducibility. The latter result was largely improved by the Limit Theorem of Barmpalias and Lewis-Pye [2], which asserts that for given left-c.e. reals $α$ and $β$ where $β$ is Martin-Löf random, for all left-approximations of $α$ and $β$ as above, the ratios $\frac{α-a_n}{β-b_n}$ converge to the same limit.

Though the original definition of Solovay reducibility applies to all reals, Solovay reducibility is considered to be badly behaved on the class of all reals. Accordingly, various variants of Solovay reducibility have been proposed, including variants defined via real-valued functions by Kumabe, Miyabe, and Suzuki [8] and a monotone variant by Titov [19]. It is known that for the monotone variant, the Limit Theorem of Barmpalias and Lewis-Pye extends to all reals [18]. By our main result, similarly the Limit Theorem holds for all reals with respect to the reducibility cl-open introduced by Kumabe et al. [8] in 2024. The result is formulated in terms of translation functions of bounded variation, and asserts that every such function from a Martin-Löf random real $β$ to a real $α$ is left differentiable in $β$. In a setting of functions that are required to be defined on the whole unit interval and not just on the reals strictly smaller than $β$, the differentiability of computable functions of bounded variation in every Martin-Löf random real was shown by Demuth [4] in 1975; similar results for other types of computable functions and randomness notions were obtained by Brattka, Miller, and Nies [3] in 2011 and Rute [15] in 2016.

Furthermore, we deduce from the main result an equivalent characterization of Martin-Löf randomness on the set of left-c.e. reals in terms of cl-open-reducibility of a real to itself.

**2012 ACM Subject Classification**

**Keywords and phrases** Solovay reducibility, relative randomness, algorithmic randomness, Martin-Löf randomness, computable analysis, left-c.e. reals

**Digital Object Identifier** 10.4230/LIPIcs.MFCS.2025.92

**Funding** supported in part by the ANR project FLITTLA ANR-21-CE48-0023

**Acknowledgements** I want to thank the anonymous referees of MFCS 2025, as well as Laurent Bienvenu and Wolfgang Merkle, for helpful comments and corrections.

# 1 Introduction and background

## Preliminaries

We start by reviewing the concept of Solovay reducibility introduced by Solovay [17] in 1975 as a measure of relative randomness and the principal results about its connection with Martin-Löf randomness on the set of left-c.e. reals, or LEFT-CE for short. Our notation is standard. All rationals and reals are supposed to be on the interval $[0, 1)$ if not stated otherwise. A left-c.e. approximation is a strictly increasing computable approximation. Unexplained notation can be found in Downey and Hirschfeldt [5].

<figure><img src="image_3.png" /></figure>

© Ivan Titov;

licensed under Creative Commons License CC-BY 4.0

50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025).

Editors: Pawel Gawrychowski, Filip Mazowiecki, and Michał Skrzypczak; Article No. 92; pp. 92:1–92:18

Leibniz International Proceedings in Informatics

<figure><img src="image_4.png" /></figure>

LIPICS

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
92:2 Relative randomness and continuous translation functions

► **Definition 1** (Solovay, 1975). A real $\alpha$ is SOLOVAY REDUCIBLE to a real $\beta$, written $\alpha \le_S \beta$, if there exists a constant $c$ and a partially computable function $g$ from $Q$ to $Q$ such that for every $q < \beta$ it holds that

$$0 < \alpha - g(q) \downarrow < c(\beta - q). \qquad (1)$$

Solovay reducibility is meant as a measure of relative randomness in the sense that, if a real is Solovay reducible to another real, then the latter real is considered to be at least as random as the former one. For example, the upward closure of Martin-Löf random reals under $\le_S$ was proved by Solovay himself [17] in 1975.

Solovay reducibility is nowadays considered as the “standard” notion of relative Martin-Löf randomness on the set of left-c.e. reals. On the latter set, Solovay reducibility has an equivalent characterization in terms of left-c.e. approximations by Calude, Hertling, Khoussainov, and Wang [16].

► **Proposition 2** (Calude et al., 1998). A left-c.e. real $\alpha$ is Solovay reducible to a left-c.e. real $\beta$ iff there exists a constant $c$ and two strictly increasing computable sequences $a_0, a_1, \dots \to \alpha$ and $b_0, b_1, \dots \to \beta$ (called LEFT-C.E. APPROXIMATIONS of $\alpha$ and $\beta$, respectively, also written $a_0, a_1, \dots, \nearrow \alpha$ and $b_0, b_1, \dots, \nearrow \beta$) such that, for every $n$, it holds that

$$0 < \alpha - a_n < c(\beta - b_n). \qquad (2)$$

In 2001, Kučera and Slaman [9] demonstrated that Martin-Löf random reals form the greatest $\le_S$-degree within the set of left-c.e. reals.

► **Theorem 3** (Kučera-Slaman Theorem, 2001). Let $\alpha$ be a left-c.e. real and $\beta$ be a Martin-Löf random left-c.e. real. Then $\alpha$ is Solovay reducible to $\beta$.

The latter result was strengthened in 2017 by Barmpalias and Lewis-Pye [2, Theorem 1.7] by showing a limit property of translation functions from Martin-Löf random left-c.e. reals to arbitrary left-c.e. reals.

► **Theorem 4** (Barmpalias-Lewis-Pye Limit Theorem 2017). Let $\alpha$ be a left-c.e. real and $\beta$ be a Martin-Löf random left-c.e. real. Then there exists a real constant $d$ such that, for all left-c.e. approximations $a_0, a_1, \dots$ to $\alpha$ and $b_0, b_1, \dots$ to $\beta$, it holds that

$$\lim_{n \to \infty} \frac{\alpha - a_n}{\beta - b_n} = d. \qquad (3)$$

Moreover, $d = 0$ if and only if $\alpha$ is Martin-Löf nonrandom.

Note that Theorem 3 follows from Theorem 4.

Merkle and Titov [13] noticed that the Barmpalias-Lewis-Pye Limit Theorem applied for $\alpha = \beta$ implies that every Martin-Löf random left-c.e. real $\beta$ is nonspeedable, i.e., that

$$\lim_{n \to \infty} \frac{\beta - b_n}{\beta - b_{f(n)}} = 1 \quad \text{for all monotone index functions } f. \qquad (4)$$

Hölzl and Janicki proved that (4) is not equivalent to Martin-Löf randomness on the set of left-c.e. reals: there exists a Martin-Löf nonrandom left-c.e. real that is nonspeedable, i.e., satisfies (4).

Outside of the set of left-c.e. reals, Solovay reducibility is considered by several authors as “badly behaved” [5]. Accordingly, several variants of Solovay reducibility that are better
suited as a relative measure of randomness in larger classes of reals have been proposed, prominently including the 2aS-reducibility by Zheng and Rettinger [22].

Titov [18] proposed to use monotone Solovay reducibility, a variant of the Solovay reducibility where the translation function g in Definition 1 is required to be nondecreasing. Note that Solovay reducibility agrees with its monotone variant on the set of left-c.e. reals. Titov also demonstrated that, with respect to monotone Solovay reducibility, the Barmpalias-Lewis-Pye Limit Theorem extends to all reals.

**Theorem 5 (Titov, 2024).** Let $\alpha$ be a real and $\beta$ be a Martin-Löf random real. Then there exists a constant $d$ such that, for every nondecreasing translation function $g$ from $\beta$ to $\alpha$, it holds that

$$ \exists \lim_{q \uparrow \beta} \frac{\alpha - g(q)}{\beta - q} = d. \qquad (5) $$

Furthermore, Titov [18] showed that, without the additional requirement that the translation function is nondecreasing, Theorem 5 does not hold even on the set of left-c.e. reals.

In 2020, Kumabe, Miyabe, Mizusawa, and Suzuki [7] used a similar approach, where the set of admissible translation functions is restricted to nondecreasing ones. However, they proposed to use translation functions on reals instead on rationals, which are required to be computable as real functions in the sense of Weihrauch [21]. They introduced via this type of translation function a reducibility, which is equivalent to Solovay reducibility on the set of left-c.e. reals [7, Theorem 1]. In what follows, we refer to this reducibility as REAL SOLOVAY REDUCIBILITY and denote it by $\leq_S^R$.

In the second and third chapters, we analyze the notions of translation functions on rationals and on reals, respectively, separately from the corresponding reducibilities, i.e., without requiring a Solovay condition like in (1).

In the fourth and fifth chapters, we prove the Barmpalias-Lewis-Pye Limit Theorem with respect to the reducibility $\leq_{cL}^{open}$ on the set of all reals.

In the sixth chapter, we discuss the notion of self-reducibility (i.e., reducibility of a real to itself) and show an equivalent characterization of Martin-Löf randomness on LEFT-CE in terms of the $\leq_{cL}^{open}$-self-reducibility.

In order to distinguish the two mentioned concepts of translation functions, we will speak of $\mathbb{Q}$-TRANSLATION FUNCTION and $\mathbb{R}$-TRANSLATION FUNCTION for translation functions on rationals and on reals, respectively.

## 2 Translation functions on rationals

Titov [20] proposed to formalize the notion of a "translation function from $\beta$ to $\alpha$", which is a function that fulfills the conditions of Definition 1 with the distance property (1) omitted. We start the studies of Solovay reducibility by formally defining translation function on rationals and introducing the relation "there exists a translation function of rationals from $\beta$ to $\alpha$" between reals $\alpha$ and $\beta$.

**Definition 6.** A $\mathbb{Q}$-TRANSLATION FUNCTION from a real $\beta$ to a real $\alpha$ is a partially computable function $g$ from the set $\mathbb{Q} \cap [0, 1)$ to itself such that, for all $q < \beta$, the value $g(q)$ is defined and fulfills $g(q) < \alpha$, and it holds that

$$ \lim_{q \uparrow \beta} g(q) = \alpha, \qquad (6) $$
92:4 Relative randomness and continuous translation functions

where $\lim_{q \uparrow \beta}$ denotes the left limit.

We write $\alpha \leq_{tf}^{\mathbb{Q}} \beta$ if there exists a $\mathbb{Q}$-translation function from $\beta$ to $\alpha$ and $\alpha \leq_{tf}^{\mathbb{mQ}} \beta$ if there exists a nondecreasing $\mathbb{Q}$-translation function from $\beta$ to $\alpha$.

First, it is easy to see that both $\leq_{tf}^{\mathbb{Q}}$ and $\leq_{tf}^{\mathbb{mQ}}$ are reflexive and transitive; thus, they are preorders that form degree structures on $\mathbb{R}$. By [20, Corollary 1 and Proposition 3], the relation $\leq_{tf}^{\mathbb{Q}}$ is not symmetric and strictly weaker than $\leq_{tf}^{\mathbb{mQ}}$. The non-symmetry of $\leq_{tf}^{\mathbb{mQ}}$ is implied by the following proposition. We omit the proof due to space restrictions.

**Proposition 7.** There exist two d.c.e. reals $\alpha$ and $\beta$ such that $\alpha \leq_{tf}^{\mathbb{mQ}} \beta$ but $\beta \not\leq_{tf}^{\mathbb{mQ}} \alpha$.

In other words, outside of the set of left-c.e. reals, it is neither always possible to "monotonize" a $\mathbb{Q}$-translation function nor to find a monotone $\mathbb{Q}$-translation function from $\alpha$ to $\beta$ from a given monotone $\mathbb{Q}$-translation function from $\beta$ to $\alpha$.

3 Translation functions on reals

In 2020, Kumabe, Miyabe, Mizusawa, and Suzuki [7] have found a characterization of Solovay reducibility on LEFT-CE that, instead of the translation functions on rationals, uses the translation functions on reals.

We start to review their approach by recalling the notion of a computable function on reals from the viewpoint of computable analysis. For unexplained notions in the next section, see [21].

3.1 Computability on the real numbers

**Definition 8.** A sequence $q_0, q_1, \dots$ of rationals is called **EFFECTIVE APPROXIMATION** if it
fulfills $|q_n - q_{n+1}| < 2^{-n}$ for every $n$.

Since every effective approximation $q_0, q_1, \dots$ is a Cauchy sequence, it converges to some
limit point $x \in \mathbb{R}$, and, for this $x$, we also say that $q_0, q_1, \dots$ is an **EFFECTIVE APPROXIMATION**
**OF** $x$.

Now, informally speaking, we call a real function $f$ computable if there exists a machine
that, for every (infinite) effective approximation of a real $x$ in its domain, returns some
(infinite) effective approximation of $f(x)$. The class of Turing machines that, using an infinite
sequence of finite strings (in our case, encoded rationals) as an oracle, returns another
sequence of finite strings was firstly formalized by Grzegorczyk [6] and, independently, by
Lacombe [10, 11, 12] in 1955. For further explanations, see the monograph by Weihrauch [21,
Chapter 2], where they are called "Turing machines of Type 2". In what follows, we give the
formal definition of a computable real function using a notion of Turing machine of Type 2
specified for the sequences of rationals.

**Definition 9 (Weihrauch, 2000).** A TURING MACHINE *M* OF TYPE 2 is an oracle Turing machine that, for every oracle (*p*₀, *p*₁, ...), where *p*₀, *p*₁, ... are (appropriately finitely encoded) rationals, produces either an infinite sequence of rationals (*q*₀, *q*₁, ...); in this case, we say that *M* RETURNS THE SEQUENCE (*q*₀, *q*₁, ...) FROM THE INPUT (*p*₀, *p*₁, ...); or a finite set of rationals (*q*₀, *q*₁, ..., *q*ₙ); in the latter case, we say that *M* (*p*₀, *p*₁, ...) IS UNDEFINED.

A real function $f$ from some subset of $\mathbb{R}$ to $\mathbb{R}$ is **COMPUTABLE** on some set $X \subseteq \text{dom}(f)$ if there exists an oracle Turing machine $M$ such that, for every $x \in X$ and every effective approximation $p_0, p_1, \dots$ that converges to $x$, $M(p_0, p_1, \dots)$ returns an effective approximation $(q_0, q_1, \dots)$ of $f(x)$.
By [21, Corollary 4.3.1], computability on reals implies continuity.

► **Proposition 10.** Every real function, which is computable on some interval $[a, b]$, is continuous in every point in $(a, b)$.

The following proposition is straightforwardly implied by [21, Corollary 6.2.5].

► **Proposition 11.** If a real function $g$ is computable on the set $[a, b)$, then the maximum function $h(x) = \max\{g(y) : a \le y \le x\}$, is computable on $[a, b)$.

Differentiability of computable functions on reals have strong connections to algorithmic randomness. In 1975, Demuth [4] proved that Martin-Löf random reals are those in which all computable function of bounded variation, see Section 4.2, are differentiable. Similar characterizations for other types of randomness have been found by Brattka, Miller, and Nies [3, computable and weak 2-randomness] and Rute [15, Schnorr randomness]. We summarize all mentioned results in the following theorem.

► **Theorem 12.** 1. A real on $[0, 1]$ is weakly 2-random iff every almost everywhere differentiable function that is computable on $[0, 1]$ is differentiable in it.

2. A real on $[0, 1]$ is Martin-Löf random iff every real function of bounded variation that is computable on $[0, 1]$ is differentiable in it.

3. A real on $[0, 1]$ is computably random iff every nondecreasing real function that is computable on $[0, 1]$ is differentiable in it.

4. A real on $[0, 1]$ is Schnorr random iff every absolutely continuous function that is computable in the variation norm on $[0, 1]$ is differentiable in it.

## 3.2 Variants of translation functions on reals

Kumabe, Miyabe, Mizusawa, and Suzuki [7, Theorem 1] characterized Solovay reducibility on LEFT-CE using different versions of translation functions on reals.

In a similar way as for translation functions on rationals, we start to explore these reducibilities. by introducing the notions of an “R-translation function” and a “weakly R-translation function” formalized by Titov [20], which do not require monotonicity.

► **Definition 13.** A WEAKLY R-TRANSLATION FUNCTION from a real $\beta$ to a real $\alpha$ is a real function $f$ which is computable on the interval $[0, \beta)$ and satisfies

$$ \lim_{x \uparrow \beta} f(x) = \alpha. \qquad (7) $$

An R-TRANSLATION FUNCTION from a real $\beta$ to a real $\alpha$ is a weakly R-translation function from $\beta$ to $\alpha$ that maps $[0, \beta)$ to the interval $[0, \alpha)$. We write $\alpha \le_{\text{tf}}^{\mathbb{R}} \beta$ if there exists a R-translation function from $\beta$ to $\alpha$.

It is easy to see that $\le_{\text{tf}}^{\mathbb{R}}$ is a preorder that induces a degree structure. In contrast to $\le_{\text{tf}}^{\emptyset}$, the restriction of R-translation functions to only nondecreasing ones does not induce any stricter relation, as we will see in the next proposition.

► **Proposition 14.** Let $f$ be a computable R-translation function on reals from $\beta$ to $\alpha$. Then, the function $h(x) = \max\{f(y) : y \le x\}$ is a nondecreasing computable R-translation function from $\beta$ to $\alpha$.
92:6 Relative randomness and continuous translation functions

Proof. The function $h$ defined as in the proposition statement is computable (in the sense of Definition 9) by Proposition 11. Moreover, $h$ is obviously nondecreasing, and it holds that

$$ \text{for every } x < \beta, \text{ there exists } y \in [0, \beta) \text{ such that } h(x) = f(y) < \alpha. \qquad (8) $$

Moreover, we have $\lim_{x \nearrow \beta} h(x) = \alpha$ by the following argument:

$$ \text{lim}_{x \nearrow \beta} h(x) = \alpha \text{ since } \lim_{x \nearrow \beta} \inf h(x) \geq \liminf_{x \nearrow \beta} f(x) = \lim_{x \nearrow \beta} f(x) = \alpha \text{ by (7)}; $$

$$ \text{lim sup}_{x \nearrow \beta} h(x) \leq \alpha \text{ by (8).} $$

Thus, $h$ is a nondecreasing $\mathbb{R}$-translation function from $\beta$ to $\alpha$.

<figure><img src="image_5.png" /></figure>

3.3 Reducibilities defined via translation function on reals

Kumabe et al. introduced in 2020 [7, Definition 9] and 2024 [8, Definition 5.1] two new types of reducibility by requiring the $\mathbb{R}$-translation functions and weakly $\mathbb{R}$-translation functions, respectively, to be Lipschitz continuous (note that replacing the requirement (1) in the definition of Solovay reducibility by the requirement for the $\mathbb{Q}$-translation $g$ to be Lipschitz continuous yields a reducibility notion which is equivalent to $\leq_S$ on LEFT-CE; for a formal proof of this fact, see [20, Proposition 1]). In what follows, we give the formal definition of these reducibility; where the reducibility denoted by Kumabe et al. as “L2” obtains a more intuitive name “real Solovay reducibility”.

► **Definition 15** (Kumabe et al., 2020; Kumabe et al., 2024). A real $\alpha$ is REAL SOLOVAY REDUCIBLE to a real $\beta$, written $\alpha \leq_S^\mathbb{R} \beta$, if there exists a Lipschitz continuous $\mathbb{R}$-translation function from $\beta$ to $\alpha$.

A real $\alpha$ is CL-OPEN REDUCIBLE to a real $\beta$, written $\alpha \leq_{cL}^{\text{open}} \beta$, if there exists a Lipschitz continuous weakly $\mathbb{R}$-translation function from $\beta$ to $\alpha$.

Titov [20, Corollary 3] has also shown that the additional requirement for the $\mathbb{R}$-translation function in the latter definition to be nondecreasing (Kumabe et al. denoted [7, Definition 9] the resulting reducibility “L1”) does not induce any strictly stronger reducibility on $\mathbb{R}$ than $\leq_S^\mathbb{R}$.

► **Proposition 16** (Titov, 2025). If $\alpha \leq_S^\mathbb{R} \beta$ for two reals $\alpha$ and $\beta$, then $\alpha \leq_S^\mathbb{R} \beta$ via a non-decreasing $\mathbb{R}$-translation function.

In the latter definitions, the Lipschitz continuity requirement can be replaced by a “localized” version of Lipschitz continuity, where instead of arbitrary pairs of arguments, we consider only pairs with second component $\beta$, similarly to the inequality (1) for translation functions on rationals.

► **Proposition 17.** For all reals $\alpha$ and $\beta$, the following equivalences hold:

1. $\alpha \leq_S^\mathbb{R} \beta$ iff there exists a constant $c$ an $\mathbb{R}$-translation function $f$ from $\beta$ to $\alpha$ that fulfills
$$ \frac{\alpha - f(x)}{\beta - x} < c. \qquad (9) $$

2. $\alpha \leq_{cL}^{\text{open}} \beta$ iff there exists a constant $c$ and a weakly $\mathbb{R}$-translation function $f$ from $\beta$ to $\alpha$ that fulfills

$$ \frac{|\alpha - f(x)|}{\beta - x} < c. \qquad (10) $$
**Proof.** Direction = ⇒ is straightforward in both equivalences since every Lipschitz continuous weakly $\mathbb{R}$-translation function $f$ from $\beta$ to $\alpha$ fulfills (10) with the value of $c$ greater than Lipschitz constant of $f$. In case $f$ maps $[0, \beta)$ to $[0, \alpha)$, we also obtain (9) from (10) since it holds $|\alpha - f(x)| = \alpha - f(x)$ for all $x \in [0, \beta)$.

241

242

243

244

The inverse directions will be obtained for every equivalence separately: first, let $f$ be an $\mathbb{R}$-translation function $f$ that fulfills (9). Then the function $g(x) = \min\{f(y) : y \le x\}$ is, by Proposition 14, is a nondecreasing $\mathbb{R}$-translation function from $\beta$ to $\alpha$ that still fulfills (9). Hence, the function $h(y) = \min\{g(y) + c(y-x) : y \le x\}$ witnesses $\alpha \le \beta$.

245

246

247

248

For a weakly $\mathbb{R}$-translation function $\tilde{f}$ that fulfills (9), we define

249

$$ \tilde{g}(x) = \min\{\tilde{f}(y) + d(x-y) : y \in [0, x]\} \quad \text{and} $$

250

$$ \tilde{h}(x) = \max\{\tilde{g}(y) - d(x-y) : y \in [0, x]\}. $$

251

Then $\tilde{h}$ is a weakly $\mathbb{R}$-translation function that witnesses $\alpha \le \beta$.

<figure><img src="image_6.png" /></figure>

252

We will refer to the equalities (9) and (10) as SOLOVAY INEQUALITY and WEAK SOLOVAY INEQUALITY, respectively.

253

254

By [7, Theorem 1] and by [8, Observation 5.3], respectively, the reducibilities $\le_S^\mathbb{R}$ and $\le_{cL}^{\text{open}}$ are equivalent to the Solovay reducibility $\le_S$ on the set of left-c.e. reals, and, by [20, Theorem 1], there are implied by $\le_S$ on $\mathbb{R}$ and $\mathbb{R} \setminus \text{COMP}$, respectively.

255

256

257

**▶ Theorem 18 (Titov, 2025).** The reducibility $\le_S$ implies $\le_S^\mathbb{R}$ on all but computable reals and $\le_{cL}^{\text{open}}$ on all reals.

258

259

# 4 Preliminaries to the Barmpalias-Lewis-Pye Limit Theorem for weakly $\mathbb{R}$-translation functions

260

261

## 4.1 Previous results

262

The characterization of Solovay reducibility given in Proposition 2 gave a new start to research of the Solovay reducibility because of its close connection with the construction of Martin-Löf and Solovay randomness tests.

263

264

265

In 2017, Miller [14] divided the Barmpalias-Lewis-Pye Limit Theorem into two logically independent statements that we denote by (KS) and (BLP) in what follows.

266

267

(KS) If there are two left-c.e. approximations $a_0, a_1, \dots$ and $b_0, b_1, \dots$ of a left-c.e. real $\alpha$ and a Martin-Löf random left-c.e. real $\beta$, respectively, then they witness the Solovay reducibility $\alpha \le_S \beta$ in the sense of Proposition 2.

268

269

270

This can be considered as a reformulation of the Kučera–Slaman Theorem (which motivates the choice of the acronym “KS”), even quite strengthened since the Solovay reducibility is witnessed by every pair of left-c.e. approximations of $\alpha$ and $\beta$, respectively. For a direct proof of this statement, see [14, Lemma 1.1].

271

272

273

274

(BLP) For every left-c.e. real $\alpha$ and Martin-Löf random left-c.e. real $\beta$, there exists a constant $d$ such that, for every left-c.e. approximations $a_0, a_1, \dots, \uparrow \alpha$ and $b_0, b_1, \dots, \uparrow \beta$ that witness the Solovay reducibility $\alpha \le_S \beta$ in the sense of Proposition 2 with some constant $c$, (3) holds.

275

276

277

278

Moreover, $d = 0$ if and only if $\alpha$ is Martin-Löf nonrandom.

279

For the direct proof of this statement, see [14, Lemma 1.2]. It is easy to see that both statements together imply exactly Theorem 4.

280

281

In the remainder of this chapter, we state each of them on $\mathbb{R}$ relative to $\le_{cL}^{\text{open}}$ using the concept of total variation of a function on reals that we recall in what follows.

282

283
92:8 Relative randomness and continuous translation functions

4.2 Total variation

The connection between functions of bounded variation on the compact interval and Martin-Löf randomness has been discovered already by Demuth, see Theorem 12(2).

In what follows, we recall the definition of functions of bounded variation defined in an arbitrary domain.

**Definition 19.** A FINITE PARTITION of a bounded set $A \subseteq \mathbb{R}$ is a tuple of finitely many reals $(x_0, \dots, x_n)$ where $n \in \mathbb{N}$ such that

$$ a < x_0 < \dots < x_n < b \quad \text{and} \quad x_i \in A \text{ for all } i \in \{0, \dots, n\}. \qquad (11) $$

The TOTAL VARIATION $V_f$ of a real function $f: \subseteq \mathbb{R} \to \mathbb{R}$ is the quantity

$$ V_f = \sup_{(x_0, \dots, x_n) \in \mathcal{P}} \sum_{i=0}^{n-1} |f(x_{i+1}) - f(x_i)|, \qquad (12) $$

where $\mathcal{P}$ is the set of all partitions of $\text{dom}(f)$.

We say that $f$ is OF BOUNDED VARIATION if $V_f < \infty$, and OF UNBOUNDED VARIATION otherwise.

5 Barmmalas-Lewis-Pye Theorem for weakly $\mathbb{R}$-translation functions

**Theorem 20.** Let $\alpha$ and $\beta$ be reals such that $\beta$ is Martin-Löf random. Then for every weakly $\mathbb{R}$-translation function of bounded variation $f$ from $\beta$ to $\alpha$, it holds that

$$ \lim_{x \uparrow \beta} \frac{\alpha - f(x)}{\beta - x} = d. \qquad (13) $$

Moreover, in case such function $f$ exists and $d \neq 0$, then $\alpha$ is Martin-Löf random as well, and it holds $\alpha \equiv_S \beta$.

**Remark 21.** In Theorem 20, the requirement for the function $f$ cannot be omitted even for left-c.e. reals $\alpha$ and $\beta$. Indeed, for every left-c.e. approximation $b_0, b_1, \dots$ of a Martin-Löf random left-c.e real $\beta$, one can easily construct an $\mathbb{R}$-translation function from $\beta$ to $\beta$, such that

$$ \limsup_{x \uparrow \beta} \frac{\beta - f(x)}{\beta - x} \geq \limsup_{n \to \infty} \frac{\beta - f(b_n)}{\beta - b_n} = \infty, $$

hence the theorem statement (13) for the function $f$ and $\alpha = \beta$ does not hold. We leave the exact construction as an exercise for the reader.

**Remark 22.** Theorem 20 is a strengthening of the “only if”-part of Theorem 12 since, in the condition of Theorem 20, the function $f$ is not required to be defined (or computable) in the point $\beta$.

**Proof.** Let $\alpha$ and $\beta$ be two real on $[0, 1)$, and let $f$ be a weakly $\mathbb{R}$-translation function of bounded variation $V_f$ from $\beta$ to $\alpha$ computed by a Turing machine $M$ of Type 2.

We organize the proof in the manner of Miller [14] by showing consequently that the ratio in (13) is bounded, that this ratio has a left limit in $\beta$, and that this limit does not depend on the choice of $f$. Finally, we consider the case $d = 0$.
## Outline of the proof

1. In Paragraph 5.1, we define two functions $f^-$ and $f^+$ from rationals to rationals that have the same domain and return the value of $f$ with a convenient precision.

2. In Paragraph 5.2, we prove that $f$ fulfills weak Solovay inequality (10) as follows: using $f^-$ and $f^+$, we define two Martin-Löf tests $S$ and $T$ whose every level will be constructed by computing in every next enumeration step of the domain of $f^-$ and $f^+$ a finite test that extends a test constructed in the previous step. Then $\beta$ should pass both tests by its Martin-Löf randomness, hence, for some $i$, the $i$th levels of both tests do not contain $\beta$. Due to the specific construction of the tests, it will imply the weak Solovay inequality for $f$ with an appropriate Solovay constant. Finally, we turn $f$ into a Lipschitz continuous weakly $\mathbb{R}$-translation function from $\beta$ to $\alpha$. During the whole construction, we will use technical claims whose proofs are omitted due to space considerations.
Note that, by Proposition 17, this part implies as a corollary that $\alpha \le_{cL}^{open} \beta$.

The part proves a generalization of the statement (**KS**) on all reals for weakly $\mathbb{R}$-translation functions. On left-c.e. reals, it easily implies (**KS**).

3. In Paragraph 5.3, we prove that, for every function $f$ that fulfills (10), there exists a constant $d$ that fulfills (13) by contradiction: supposing the converse, we define two functions $f^-$ and $f^+$ from rationals to rationals that have the same domain and return values of $f$ with convenient precision. Then we define a Solovay test $S$ whose every level will be a finite test computed in every next enumeration step of the domain of $f^-$ and $f^+$ that extends a test computed in the previous step. Due to the specific construction of the test, it will imply that either contain $\beta$ infinitely many times, which contradicts its Martin-Löf randomness.
This is the main part of the proof, which is based on the proof of [18, Section 2.2] adapted for $\mathbb{R}$-translation functions.

4. In Paragraph 5.4, we prove the uniqueness of $d$ by contradiction: supposing the existence of two different functions $f_1$ and $f_2$ witnessing $\alpha \le_{cL}^{open} \beta$ with the different values of $d$, we obtain an effective approximation of $\beta$ (which cannot exist for Martin-Löf random reals) by using the computable function $f_1 - f_2$. This part is directly implied by properties of computable real-valued functions.

5. Finally, in Paragraph 5.5 in case $d \neq 0$, we construct a function $\tilde{f}$ witnessing $\beta \le_S \alpha$ by inverting $f$. This implies the Martin-Löf randomness of $\alpha$ since, by [20, Proposition 9(a)], Martin-Löf random reals are $\le_{cL}^{open}$-closed upwards in $\mathbb{R}$. This part has no analogues for Solovay reducibility via rational translation functions because, by Proposition 7, strictly increasing translation functions on rationals are not always invertible.
Note that the latter case also implies $\alpha = \beta$.

The latter three parts together build a generalization of the statement (**BLP**) on all reals for weakly $\mathbb{R}$-translation functions. On left-c.e. reals, they easily imply (**BLP**).

## Notation

In the remainder of this proof and unless explicitly stated otherwise, for two reals $a < b$, the length of the interval $I = [a, b]$ will be denoted by $|I|$, and the notation $[b, a]$ will denote an empty interval with length 0. A TEST SET is a tuple of pairs of rationals $Q = (\binom{r_0}{s_0}, \dots, \binom{r_n}{s_n})$ if it fulfills the inequality $s_0 \le s_1 \le \dots \le s_n$, and a FINITE TEST is an empty set or a tuple $A = (U_0, \dots, U_m)$ with $m \ge 0$ where the $U_i$ are not necessarily distinct nonempty intervals.
92:10 Relative randomness and continuous translation functions

We also say that a finite test A IS COVERED by another finite test B, written A $\preceq$ B, if
the union of all intervals contained in the tuple A is covered by the union of all intervals
contained in the tuple B:

$$
A \preceq B \quad :\Leftrightarrow \quad \bigcup_{I \in A} I \subseteq \bigcup_{I \in B} I. \tag{14}
$$

5.1 From functions on reals to functions on rationals

Let $p_0, p_1, \dots$ be an enumeration of all rationals in $[0, 1]$, and define a two-argument-
function $g : \subseteq \mathbb{Q}|_{[0,1)} \times \mathbb{N} \to \mathbb{Q}$ as follows: for every $p$, let

$$
g(p, n) = r_{2n} \text{ if } \begin{cases} (M^{(p,p,\dots)} \upharpoonright 2n) \downarrow = (r_1, \dots, r_{2n}) \\ r_{i+1} - r_i < 2^i \text{ for every } i \in \{1, \dots, 2n-1\} \end{cases}
$$

(remind that $M$ is a Turing machine of Type 2 that computes $f$) and $(p, n) \uparrow$ otherwise. In
particular, if the value of $f(p)$ is defined (which holds, inter alia, for all rationals in $[0, \beta)$),
then, for all $n$, $g(p, n)$ halts and returns it with accuracy $2^{-2n}$.

Next, let $q_0, q_1, \dots$ be a sub-sequence of $p_0, p_1, \dots$ obtained by the following dove-
tailing: At the step $i$, add into the sequence $(q_0, q_1, \dots)$ some $p_k$ such that $g(p_k, 2i)$ is
defined and the sequence $(q_0, q_1, \dots)$ does still not contain $p_k$. By the previous discussion,
all rationals in $[0, \beta)$ will be enumerated into $q_0, q_1, \dots$, hence the functions

$$
\tilde{f}(q) = g(q_n, 2n) \quad \text{and} \quad \begin{cases} f^{-}(q) = \tilde{f}(q_n) - 2^{-2n} \\ f^{+}(q) = \tilde{f}(q_n) + 2^{-2n} \end{cases} \quad \text{if there exists } n \text{ such that } q = q_n \quad (15)
$$

are defined for all $q_n$, in particular, on the whole set $\mathbb{Q}|_{[0,\beta)}$.

It obviously holds for every $n$ that

$$
|\tilde{f}(q_n) - f(q_n)| = |g(q_n, 2n) - f(q_n)| \le 2^{-2n}, \text{ hence } f^{-}(q_n) \le \tilde{f}(q_n) \le f^{+}(q_n), \quad (16)
$$

wherein the sum of distances between $f^+(q)$ and $f^-(q)$ for all their arguments is bounded
from above:

$$
\sum_{n \in \mathbb{N}} |f^{+}(q_n) - f^{-}(q_n)| \le \sum_{n \in \mathbb{N}} 2 \cdot 2^{-2n} = \frac{8}{3}. \qquad (17)
$$

The next two claims describe the further properties of functions $\tilde{f}$, $f^+$, and $f^-$.
The first one follows from the definition of $V_f$ and (16), the second one from (16) and the density of both functions on $[0, \beta)$.

▷ Claim 23. Let $n$ be a natural, and let the tuple $(q_0^n, \dots, q_n^n)$ be the set $\{q_0, \dots, q_n\}$ sorted increasingly. Then we have

$$
\sum_{i=0}^{n-1} |\tilde{f}(q_{i+1}^n) - \tilde{f}(q_i^n)| \le V_f + \frac{8}{3} < \infty. \quad (18)
$$

▷ Claim 24. The value $\alpha$ is the left limit of function $\tilde{f}$ in $\beta$, i.e.,

$$
\exists \lim_{q \uparrow \beta} \tilde{f}(q) = \alpha. \tag{19}
$$
## 5.2 f fulfills the weak Solovay inequality

Now, using the functions $\tilde{f}$ and $g$, we construct two Martin-Löf tests $S$ and $T$ by applying in every enumeration step of $q_0, q_1, \dots$ the same algorithm that will be described in what follows on an appropriate test set.

### A single stage of the construction

Fix a natural $i$ (called LEVEL) and a test set $Q = \left( \begin{pmatrix} a_0 \\ b_0 \end{pmatrix}, \begin{pmatrix} a_1 \\ b_1 \end{pmatrix}, \dots, \begin{pmatrix} a_n \\ b_n \end{pmatrix} \right)$ where $n \ge 0$.

We describe the construction of the finite test $Test_i(Q)$, which is a lightly modified version of a construction used by Titov [18, Theorem 2.1].

For every two indices $k, m$, such that $0 \le k < m \le n$, define the interval

$$ I[k, m] := R\left(\begin{pmatrix} a_k \\ b_k \end{pmatrix}, \begin{pmatrix} a_m \\ b_m \end{pmatrix}\right) := \begin{cases} \left[b_m, b_k + \frac{a_m - a_k}{2^{i+1}}\right] & \text{if } \frac{a_m - a_k}{b_m - b_k} \ge 2^{i+1}, \\ \emptyset & \text{otherwise,} \end{cases} \quad (20) $$

and put the intersection of $I[k, m]$ with the unit interval $[0, 1]$ into the test $Test_i(Q)$, obtaining

$$ Cover(Test_i(Q)) = \left( \bigcup_{k,m \in \{0, \dots, n\}: k < m} I[k, m] \right) \cap [0, 1]. \quad (21) $$

Further, for technical reasons, for all $k, m$ such that $0 \le m \le k \le n$, set $I[k, m] = \emptyset$. We will also write $I^i[k, m]$ for $I[k, m]$ in case the level $i$ is not clear from the context.

Then, this construction fulfills the inclusion properties by levers and test sets, respectively, described in the next claim.

### Claim 25. For every test set $P$ and every two indices $i$ and $j$, $i < j$ implies that $Test_j(P) \preceq Test_i(P)$.

For every index $i$ and every two test sets $P$ and $Q$, $P \subseteq Q$ implies that $Test_i(P) \preceq Test_i(Q)$ for every index $i$.

The claim describes the inclusion properties of particular intervals of $Test_i(Q)$.

### Claim 26. For every two indices $k$ and $l$ where $0 \le k < l \le n$, the following implications hold:

$$ \frac{a_l - a_k}{b_l - b_k} \le 2^{i+1} \quad \Rightarrow \quad \forall m > l(I[k, m] \subseteq I[l, m]), \quad (22) $$

$$ \frac{a_l - a_k}{b_l - b_k} \ge 2^{i+1} \quad \Rightarrow \quad \forall m(I[k, m] \supseteq I[l, m]). \quad (23) $$

In what follows, we defined an index subset $i_0, \dots, i_s$ of $0, \dots, n$ and see that every level $Test_i(Q)$ of $Test(Q)$ is a disjoint union of some intervals defined via $i_0, \dots, i_s$.

Let $0 = i_0 < i_1 < \dots < i_s$ be the indices in the range $0, \dots, n$ such that

$$ \frac{a_m - a_{i_s}}{b_m - b_{i_s}} > 2^{i+1} \quad \text{for all} \quad m \in \{i_s, \dots, n\} \quad (24) $$

and, for every $j \in \{0, \dots, s-1\}$,

$$ \frac{a_{i_{j+1}} - a_{i_j}}{b_{i_{j+1}} - b_{i_j}} \le 2^{i+1}, \quad (25) $$

$$ \frac{a_m - a_{i_j}}{b_m - b_{i_j}} > 2^{i+1} \quad \text{for all} \quad m \in \{i_j + 1, \dots, i_{j+1} - 1\}. \quad (26) $$
92:12 Relative randomness and continuous translation functions

Further, due to the technical reasons, we fix an additional index $i_{s+1} = n + 1$ (hence $i_{s+1} - 1 = n$) and set $q_{n+1} = 1$ and $g(q_{n+1}) = 1$, so (24) is nothing but (26) for $j = s$.

Next, define for every $j$ from 0 to $s$ the index $h_j$ in the range $i_j, \dots, s$ such that

$$a_{h_j} = \max\{a_h : i_j \le h < i_{j+1}\}. \qquad (27)$$

► Claim 27. If a real $x$ is not contained in any interval $[b_{i_j}, b_{i_j} + \frac{a_{h_j} - a_{i_j}}{2^{i+1}}]$ for all $j$ in the range $0, \dots, s$, then we have $x \notin I[k, m]$ for all $k$ and $m$.

By (21) the latter claim implies as a corollary that

$$\mathrm{Cover}(\mathrm{Test}(Q_i)) \subseteq \bigcup_{j \in \{0, \dots, s\}} \left[ b_{i_j}, b_{i_j} + \frac{a_{h_i} - a_{i_j}}{2^{i+1}} \right]. \qquad (28)$$

Construction and properties of two Martin-Löf tests S and T

We will construct two Martin-Löf tests $T$ with levels $S_0, S_1, \dots$ and $T$ with levels $T_0, T_1, \dots$ iteratively: first, at stage 0, we initialize for every natural $i$ the levels $S_0^0, S_1^0, \dots$ and $T_0^0, T_1^0, \dots$ as empty sets; in every next stage $n > 0$, we define for every natural $i$ the test sets

$$Q_n = \left( \begin{pmatrix} f^-(q_0^n) \\ q_0^n \end{pmatrix}, \begin{pmatrix} f^+(q_0^n) \\ q_0^n \end{pmatrix}, \begin{pmatrix} f^-(q_1^n) \\ q_1^n \end{pmatrix}, \begin{pmatrix} f^+(q_1^n) \\ q_1^n \end{pmatrix}, \dots, \begin{pmatrix} f^-(q_n^n) \\ q_n^n \end{pmatrix}, \begin{pmatrix} f^+(q_n^n) \\ q_n^n \end{pmatrix} \right), (29)$$

$$Q'_n = \left( \begin{pmatrix} 1 - f^+(q_0^n) \\ q_0^n \end{pmatrix}, \begin{pmatrix} 1 - f^-(q_0^n) \\ q_0^n \end{pmatrix}, \dots, \begin{pmatrix} 1 - f^+(q_n^n) \\ q_n^n \end{pmatrix}, \begin{pmatrix} 1 - f^-(q_n^n) \\ q_n^n \end{pmatrix} \right). \qquad (30)$$

In particular, we directly obtain then the following observation:

$$Q_{n-1} \subseteq Q_n \quad \text{and} \quad Q'_{n-1} \subseteq Q_n \quad \text{for all } n > 0. \qquad (31)$$

Next, for every $i$ and $n$, we define the finite tests

$$S_i^n = \mathrm{Test}_i(Q_n) \quad \text{and} \quad T_i^n = \mathrm{Test}_i(Q'_n).$$

Then the second statement of Claim 25 implies that

$$S_i^{n-1} \preceq S_i^n, S_{i-1}^n \preceq S_i^n, T_i^{n-1} \preceq T_i^n, T_{i-1}^n \preceq T_i^n \text{ for all } i, n > 0.$$

Now, for all $i$, we can construct an infinite test $S_i$ as follows: by (31), we can represent for every $n > 0$ the set $\mathrm{Cover}(S_i^n) \setminus \mathrm{Cover}(S_i^n)$ as a disjoint union of finitely many intervals (i.e., a finite test) $X_i^n$, wherein a list of intervals is computable in $i$ and $n$ because the same holds for $S_i^n$ and $S_i^{n-1}$. So, we list the intervals in the finite sets $X_i^0, X_i^1, \dots$ in the infinite $S_i$. An infinite test $T_i$ can be constructed likewise for every $i$.

As a next claim, we give an upper bound for the measure of the union of intervals in every constructed finite test that is implied by Claim 27.

► Claim 28. There is a constant $c$ such that, for every naturals $i$ and $n$, the measure of the union of all intervals from $S_i^n$ and the measure of the union of all intervals from $T_i^n$ are bounded from above by $2^{-ic}$.

By Claim 28, there exists a natural $m > 0$ such that, for every $n > 0$, the measures of $\mathrm{Cover}(S_i^n)$ and $\mathrm{Cover}(T_i^n)$ are both bounded from above by $2^{m-i}$; therefore, by the compactness argument, the same holds for $\mathrm{Cover}(S_i)$ and $\mathrm{Cover}(T_i)$. Thus, the tests $(S_{m+1}, S_{m+2}, \dots)$ and $(T_{m+1}, T_{m+2}, \dots)$ are Martin-Löf tests, wherein, by the first statement of Claim 25, it holds that

$$\mathrm{Cover}(S_{m+1}) \supseteq \mathrm{Cover}(S_{m+2}) \supseteq \dots \quad \text{and} \quad \mathrm{Cover}(T_{m+1}) \supseteq \mathrm{Cover}(T_{m+2}) \supseteq \dots \qquad (32)$$
Functions $\tilde{f}$ and $f$ fulfill the weak Solovay inequality

462

463

464

465

Since $\beta$ is Martin-Löf random, both Martin-Löf tests fail on it, hence there exist levels $i_1$ and $i_2$ such that $\beta \notin S_{i_1}$ and $\beta \notin T_{i_2}$. Therefore, by $\tilde{i} = \max\{i_1, i_2\} + 1$, it holds by (32) that

466

$$ \beta \notin \mathrm{Cover}(S_{\tilde{i}-1}) \cup \mathrm{Cover}(T_{\tilde{i}-1}). \quad (33) $$

467

468

Next, we will successively prove two claims that the functions $\tilde{f}$ and $f$, respectively, fulfill the weak Solovay condition.

469

▷ Claim 29. For all rationals $q \in [0, \beta)$, it holds that $|\alpha - \tilde{f}(q)| < 2^{\tilde{i}}(\beta - x)$.

470

▷ Claim 30. For all reals $x \in [0, \beta)$, it holds that $|\alpha - f(q)| < 2^{\tilde{i}+1}(\beta - x)$.

471

## 5.3 The limit exists

472

473

474

At that moment, we already know from the previous paragraph that $f$ fulfills weak Solovay inequality, i.e., the fraction $\frac{|\alpha - f(x)|}{\beta - x}$ is bounded on $[0, \beta)$, Now, we prove by contradiction that, for $x$ converging to $\beta$ from below, the latter fraction converges, i.e., that

475

$$ \exists \lim_{q \nearrow \beta} \frac{\alpha - f(q)}{\beta - q}. \quad (34) $$

476

477

Supposing that the left limit in (34) does not exist, by the boundedness of $\frac{|\alpha - f(x)|}{\beta - x}$ on $[0, \beta)$, we can fix two rational constants $c$ and $d$ where

478

$$ c < d, \quad d - c < 1, \quad \text{and} \quad \liminf_{x \nearrow \beta} \frac{\alpha - f(x)}{\beta - x} < c < d < \limsup_{x \nearrow \beta} \frac{\alpha - f(x)}{\beta - x} \quad (35) $$

479

and the rational

480

$$ e = d - c > 0. \quad (36) $$

481

In particular, we obtain from (35) and the right part of (16), we obtain that

482

$$ \liminf_{q \nearrow \beta} \frac{\alpha - f^{+}(q)}{\beta - q} < c < d < \limsup_{q \nearrow \beta} \frac{\alpha - f^{-}(q)}{\beta - q}. \quad (37) $$

483

484

Recall that, according to the discussion in Paragraph 5.1, the rational functions $f^{-}$ and $f^{+}$ are totally computable on $LC(\beta)$.

485

486

487

We will obtain the desired contradiction by constructing a Solovay test that fails on $e\beta$, which cannot be true since $e$ is rational and $\beta$ is Martin-Löf random. At every construction stage, we apply the algorithm by Titov [18, Section 2.2] of the test set defined below.

488

## The functions $\gamma(q)$ and $\delta(q)$

489

First, we define two partial computable functions $\gamma$ and $\delta$ that have the same domain as $\tilde{f}$:

490

$$ \gamma(q) = \tilde{f}(q) - cq \quad \text{and} \quad \delta(q) = \tilde{f}(q) - dq. $$

491

Due to $c < d$, the following claim is immediate:

492

▷ Claim 31. For every $q$ in the domain of $\tilde{f}$, we have

493

$$ \gamma(q) - \delta(q) > (d - c)q = eq > 0, \quad \text{hence} \quad \gamma(q) > \delta(q). $$

494

495

496

In particular, the partial function $\gamma - \delta$ is strictly increasing on its domain, hence, for every sequence $q_0 < q_1 < \dots$ of rationals in $[0, \beta)$ that converges to $\beta$, the values $g(q_i)$ are defined, and therefore, the values $\gamma(q_i) - \delta(q_i)$ converge strictly increasingly to $(d - c)\beta$.
92:14 Relative randomness and continuous translation functions

A single stage of the construction: definition of the test set

Let $Q = \{p_0 < \dots < p_n\}$ be a finite nonempty subset of the domain of $\tilde{f}$. Recalling that $q_0, q_1, \dots$ is an enumeration of $\text{dom}(\tilde{f})$; thus, we have $p_0 = q_{k_0}, p_1 = q_{k_1}, \dots, p_n = q_{k_n}$ for appropriate indexes $k_0, \dots, k_n$. Note that — in contrast to Paragraph 5.2 — $p_0, \dots, p_n$ don’t need to be first $n+1$ enumeration elements $q_0, \dots, q_n$ rearranged. For all $i$ in $\{0, \dots, 2n+1\}$, let

$$\delta_{2i} = \delta(p_i) - 2^{-2k_i+1} = g(p_i) - dp_i + 2^{-2k_i+1},$$

$$\gamma_{2i} = \gamma(p_i) - 2^{-2k_i+1} = g(p_i) - cp_i + 2^{-2k_i+1},$$

$$\delta_{2i+1} = \delta(p_i) + 2^{-2k_i+1} = g(p_i) - dp_i - 2^{-2k_i+1},$$

$$\gamma_{2i+1} = \gamma(p_i) + 2^{-2k_i+1} = g(p_i) - cp_i - 2^{-2k_i+1},$$

Then we set

$$M_{\text{ext}}(Q) = M((\delta_0, \gamma_0), (\delta_1, \gamma_1), \dots, (\delta_{2n+1}, \gamma_{2n+1})), \quad (38)$$

where $M((\delta_0, \gamma_0), (\delta_1, \gamma_1), \dots, (\delta_{2n+1}, \gamma_{2n+1}))$ is the finite test returned by Titov’s algorithm [18, Section 2.2] applied to the test set $M((\delta_0, \gamma_0), (\delta_1, \gamma_1), \dots, (\delta_{2n+1}, \gamma_{2n+1}))$.

Then the following claim can be obtained in the same way as the main result of [18, Section 2.2]. Its explicit proof is omitted due to space restrictions.

513 ▷ Claim 32. For $Q_n = \{q_0, q_1, \dots, q_n\}$ for every $n$, the finite sets $M_{\text{ext}}(Q_0)$, $M_{\text{ext}}(Q_1)$, \dots subsequently extend to a Solovay test that fails on $e\beta$.

5.4 The limit is unique

We prove the uniqueness of $d$ for all weakly $\mathbb{R}$-translation functions from $\beta$ to $\alpha$ by contradiction: suppose that there exist two translation functions $f$ and $g$ from $\beta$ to $\alpha$ such that the (by the previous paragraph, existing) values $\lim_{x \nearrow \beta} \frac{\alpha - f(x)}{\beta - x}$ and $\lim_{q \nearrow \beta} \frac{\alpha - g(q)}{\beta - q}$ differ. By symmetry, without loss of generality, we can then pick rationals $c$ and $d$ such that

$$\lim_{q \nearrow \beta} \frac{\alpha - g(q)}{\beta - q} < c < d < \lim_{q \nearrow \beta} \frac{\alpha - f(q)}{\beta - q}. \quad (39)$$

By (39), for every rational $b < \beta$ that is close enough to $\beta$, it holds that

$$\frac{\alpha - g(q)}{\beta - q} < c \quad \text{and} \quad d < \frac{\alpha - f(q)}{\beta - q}.$$

Then, the real function $h = g - f$ is computable on $[b, \beta)$, fulfills

$$\lim_{x \nearrow \beta} h(x) = \lim_{x \nearrow \beta} g(x) - \lim_{x \nearrow \beta} f(x) = \alpha - \alpha = 0 \quad \text{and} \quad (40)$$

$$\lim_{x \nearrow \beta} \frac{h(x)}{\beta - x} = \lim_{x \nearrow \beta} \frac{g(x) - f(x)}{\beta - x} = \lim_{x \nearrow \beta} \frac{\alpha - f(x)}{\beta - x} - \lim_{x \nearrow \beta} \frac{\alpha - g(x)}{\beta - x} = d - c > 0. \quad (41)$$

From (40) and (41), we easily obtain the computability of $\beta$.
## 5.5 Case $d = 0$

As a computable function, $f$ is continuous on $[0, \beta)$ by [21, Theorem 4.3.1].

Therefore, if $d > 0$ (the case $d < 0$ is analogous), we can fix a constant $c < d$ and a rational $b < \beta$ such that $\frac{\alpha - f(x)}{\beta - x} \in [c, d]$ for every $x \in [b, \beta]$. The function

$$h(x) = \max\{f(y), f(b) + c(y - b) : y \in [b, x]\}$$

is a strictly increasing $\mathbb{R}$-translation function of (obviously) bounded variation. Hence, its inverse $f^{-1}$ defined on $[f(b), \alpha]$ is computable by [21, Inverse function Theorem] and has a finite total variation on $[f(b), \alpha]$ (since $f$ has a finite total variation on $[b, \beta]$).

It also satisfies Solovay inequality (9) on some left neighborhood of $\alpha$ since

$$\lim_{y \succ \alpha} \frac{\beta - h(y)}{\alpha - y} = \lim_{x \succ \beta} \frac{\beta - x}{\alpha - h(x)} = \frac{1}{d},$$

hence, by Proposition 17, $\beta \leq_{cL}^{\text{open}} \alpha$.

Then $\alpha$ is Martin-Löf random because, by [20, Proposition 9(a)], the set of Martin-Löf reals is $\leq_{cL}^{\text{open}}$-closed upwards. ◀

# 6 Self-reducibility and Martin-Löf randomness

For a real $\alpha$, a $\leq_S$-SELF-REDUCIBILITY of $\alpha$ is the reducibility $\alpha \leq_S \alpha$ witnessed by some $\mathbb{Q}$-translation function from $\alpha$ to itself. For other reducibilities discussed in this paper, the self-reducibility notion can be introduced likewise.

The next characteristic of Martin-Löf randomness on the set on left-c.e. reals is implied by Theorem 5 applied for the Martin-Löf random left-c.e. reals $\alpha = \beta$. Its proof uses the concept of monotone test introduced by Barmpalias, Fang, Merkle, and Titov [1] in 2025.

**▶ Theorem 33.** For every left-c.e. real $\alpha$, the following two statements are equivalent:

1. $\alpha$ is Martin-Löf random;

2. every weak $\mathbb{R}$-translation function $f$ of bounded variation from $\alpha$ to itself has the property $\exists \lim_{x \succ \alpha} \frac{\alpha - f(x)}{\alpha - x} = 1$.

**Proof.** First, we show the direction $(1) \implies (2)$. By Theorem 5 applied for $\alpha = \beta$, the limit value

$$d = \lim_{x \succ \alpha} \frac{\alpha - f(q)}{\alpha - q}$$

exists and does not depend on the choice of $f$ witnessing $\alpha \leq_{cL}^{\text{open}} \alpha$, wherein, for $f = id$, we obviously have $d = 1$.

In order to prove $\neg (1) \implies \neg (2)$, we fix a Martin-Löf nonrandom left-c.e. real $\alpha$ and a Solovay test $S = ([l_n, r_n])_{n \in \mathbb{N}}$ that fails on $\alpha$ (i.e., $\alpha \in [l_n, r_n]$ for infinitely many $r$).

First, on the basis of $S$ and $a_0, a_1, \dots$, we construct another Solovay test $T = (l'_n, r'_n)_{n \in \mathbb{N}}$ that fails on $\alpha$ and additionally fulfills

$$l'_0 < l'_1 < l'_2 < \dots < \alpha. \qquad (42)$$

We do it by cutting the original test $S$ in the following way: starting from $i_{-1} = t_{-1} = -1$, at every step $n \geq 0$, we denote with $(i_n, t_n)$ the first index pair $(i, t)$ such that

$$i > i_{n-1}, \quad t \notin \{t_0, t_1, \dots, t_{n-1}\}, \quad \text{and} \quad l_t < a_i$$
92:16 Relative randomness and continuous translation functions

and put $[l'_n, r'_n] = [a_{i_n}, r_{t_n}]$ into the test $T$.

564

The constructed test $T$ is obviously computable and has a finite measure since $S$ has a finite measure and $[a_{i_n}, r_{t_n}] \subseteq [l_{t_n}, r_{t_n}]$; therefore, $T$ is a Solovay test. Further, (42) holds since $l'_0, l'_1, \dots$ is a sub-sequence of $a_0, a_1, \dots$.

565

566

567

Finally, for every (of infinitely many) $\tilde{t}$ such that

568

$$ \alpha \in [l_i, r_i], $$

569

we have $l_i < \alpha < r_{\tilde{t}}$ for every index $i$, hence there exists an index of a second order $\tilde{n}$ such that $\tilde{t} = t_{\tilde{n}}$ (in other words, the pair $(i_{\tilde{n}}, t_{\tilde{n}})$ where $t_{\tilde{n}} = \tilde{t}$ will be enumerated). Thus, by $a_{i_{\tilde{n}}} < \alpha$, we have $\alpha = [a_{i_{\tilde{n}}}, r_{t_{\tilde{n}}}]$. Therefore, the test $T$ fails on $\alpha$.

570

571

572

The following properties of the Solovay test $T$ can be easily obtained from (42), its finite measure, and the existence of infinitely many indices $i$ such that $\alpha \in [l'_i, r'_i]$:

573

574

$$ l'_0, l'_1, \dots \not\nearrow \alpha \quad \text{and} \quad r'_0, r'_1, \dots \to \alpha. $$

575

Then, the function $f$ defined by

576

$$ f(x) = l'_{n} - (r'_{n} - l'_{n}) + \frac{x - l'_{n}}{l'_{n+1} - l'_{n}} (l'_{n+1} - (r'_{n+1} - l'_{n+1})) \quad \text{if } x \in [l'_{n}, l'_{n+1}] \text{ for some } n, $$

577

and $f(x) = l'_0$ on $[0, l'_0]$ is a piecewise linear function that fulfills $f(l'_i) = l'_i - (r'_i - l'_i)$ for all $i \ge 0$, hence its total variation is equal to

578

579

$$ \begin{aligned} \sum_{i=0}^{n} |f(l'_{n+1}) - f(l'_{n})| &= \sum_{i=0}^{n} ((2l'_{n+1} - r'_{n+1}) - (2l'_{n} - r'_{n})) \\ &\le \sum_{i=0}^{n} (2l'_{n+1} - 2l'_{n}) + \sum_{i=0}^{n} (r'_{n} - l'_{n}) = 2(\alpha - l'_{0}) + \mu(T) < \infty, \end{aligned} $$

580

581

where $\mu(T)$ denotes the (finite) measure of the Solovay test $T$.

582

Further, $f(l'_n) < l'_n < \alpha$ for all $n$, and $\lim_{x \nearrow \alpha} f(x) = \lim_{n \to \infty} (l'_n - (r'_n - l'_n)) = 2 \lim_{n \to \infty} l'_n - \alpha$

583

$\lim_{n \to \infty} r'_n = 2\alpha - \alpha = \alpha$, hence $f$ is an $\mathbb{R}$-translation function from $\alpha$ to $\alpha$, wherein it holds that

584

585

$$ \limsup_{x \nearrow \alpha} \frac{\alpha - f(x)}{\alpha - x} \ge \limsup_{n \to \infty} \frac{(\alpha - l'_n) + (r'_n - l'_n)}{\alpha - l'_n} \ge 2, $$

586

since, for every $n$ such that $\alpha \in [l'_n, r'_n]$, the corresponding fraction is larger than 2.

587

◀

► **Remark 34.** By [19, Proposition 53], speedability can be characterized on LEFT-CE (and even *defined* outside of LEFT-CE, see [19, Chapter 5] for further information) in terms of $\le_S^m$-self-reducibility; in particular, Theorem 5 directly implies that all (not only left-c.e.) Martin-Löf random reals are nonspeedable.

588

589

590

591

In the similar manner, Theorem 33 motivates investigating an appropriate speedability notion that can be defined on $\mathbb{R}$ in terms of $\le_{cL}^{open}$-self-reducibility. That can be the point of interest for a future research.

592

593

594

References

595

1. George Barmpalias, Nan Fang, Wolfgang Merkle, and Ivan Titov. Speedability of $\Delta_2^0$ reals and computable approximations. *Unpublished draft*, 2025.

596

597
2 George Barmpalias and Andrew Lewis-Pye. Differences of halting probabilities. *Journal of Computer and System Sciences*, 89:349–360, 2017. doi:10.1016/j.jcss.2017.06.002.

598

599

3 Vasco Brattka, Joseph S. Miller, and André Nies. Randomness and differentiability. *CoRR*, abs/1104.4465, 2011. URL: http://arxiv.org/abs/1104.4465, arXiv:1104.4465.

600

601

4 Osvald Demuth. The differentiability of constructive functions of weakly bounded variation on pseudo numbers (rus. "О дифференцируемости конструктивных функций слабо ограниченной вариации на псевдочислах"). *Commentationes Mathematicae Universitatis Carolinae*, 016(3):583–599, 1975. URL: http://eudml.org/doc/16711.

602

603

604

605

5 Rod Downey and Denis Hirschfeldt. *Algorithmic Randomness and Complexity*. Springer-Verlag, Berlin, Heidelberg, 2010.

606

607

6 Andrzej Grzegorczyk. Computable functionals. *Fundamenta Mathematicae*, 42(1):168–202, 1955. URL: http://eudml.org/doc/213369.

608

609

7 Masahiro Kumabe, Kenshi Miyabe, Yuki Mizusawa, and Toshio Suzuki. Solovay reducibility and continuity. *Journal of Logic and Analysis*, 12, 12 2020. doi:10.4115/jla.2020.12.2.

610

611

8 Masahiro Kumabe, Kenshi Miyabe, and Toshio Suzuki. Solovay reducibility via Lipschitz functions and signed-digit representation. *Computability*, pages 1–27, 06 2024. doi:10.3233/COM-230486.

612

613

614

9 Antonín Kučera and Theodore Slaman. Randomness and recursive enumerability. *SIAM Journal of Computing*, 31:199–211, 07 2001. doi:10.1137/S0097539799357441.

615

616

10 Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. I. *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Paris*, 240:2478-2480, 1955.

617

618

619

11 Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. II. III. *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Paris*, 241:13-14, 151-153, 1955.

620

621

622

12 Daniel Lacombe. Remarques sur les opérateurs récursifs et sur les fonctions récursives d'une variable réelle. *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Paris*, 241:1250-1252, 1955.

623

624

625

13 Wolfgang Merkle and Ivan Titov. Speedable left-c.e. numbers. In Henning Fernau, editor, *Computer Science – Theory and Applications*, pages 303–313, Cham, 2020. Springer International Publishing.

626

627

628

14 Joseph S. Miller. On work of Barmpalias and Lewis-Pye: a derivation on the d.c.e. reals. In *Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday*, pages 644–659. Springer International Publishing, 2017. doi:10.1007/978-3-319-50062-1_39.

629

630

631

632

15 Jason Rute. Schnorr randomness for noncomputable measures. *Information and Computation*, 258:50–78, 2018. URL: https://www.sciencedirect.com/science/article/pii/S0890540117301888, doi:10.1016/j.ic.2017.10.001.

633

634

635

16 Cristian S. Calude, Peter H. Hertling, Bakhadyr Khoussainov, and Yongge Wang. Recursively enumerable reals and Chaitin Ω numbers. *Theoretical Computer Science*, 255(1):125–149, 2001. doi:10.1016/S0304-3975(99)00159-0.

636

637

638

17 Robert M. Solovay. Draft of paper (or series of papers) on Chaitin's work, 05 1975.

639

18 Ivan Titov. Extending the Limit Theorem of Barmpalias and Lewis-Pye to all reals, 2024. arXiv:2407.14445.

640

641

19 Ivan Titov. *Solovay reducibility and speedability outside of left-c.e. reals*. PhD thesis, Ruprecht-Karls-Universität Heidelberg, 2024.

642

643

20 Ivan Titov. Variants of Solovay reducibility. In Arnold Beckmann, Isabel Oitavem, and Florin Manea, editors, *Crossroads of Computability and Logic: Insights, Inspirations, and Innovations*, pages 467–481, Cham, 2025. Springer Nature Switzerland.

644

645

646

21 Klaus Weihrauch. *Computable Analysis: An Introduction*. Springer-Verlag, Berlin, Heidelberg, 2000.

647

648