Randomness versus superspeedability
Rupert Hölzl Philip Janicki Wolfgang Merkle Frank Stephan


Partial Renormalization of Quasiparticle Interactions
    Kun Chen
    April 29, 2024
=====================================================




Speedable numbers are real numbers which are algorithmically approximable from below and whose approximations can be accelerated nonuniformly. We begin this article by answering a question of Barmpalias by separating a strict subclass that we will refer to as superspeedable from the speedable numbers; for elements of this subclass, acceleration is possible  uniformly  and to an even higher degree. This new type of benign left-approximations of numbers then integrates itself into a hierarchy of other such notions studied in a growing body of recent work. We add a new perspective to this study by juxtaposing this hierachy with the well-studied hierachy of algorithmic randomness notions.




§ MOTIVATION


In theoretical computer science, the concepts of randomness and of computation speed, as well as their interactions with each other, play an important role. For example, one can study whether access to sources of random information can enable or simplify the computation of certain mathematical objects, for example by speeding up computations of difficult problems. This is a recurring paradigm of theoretical computer science, and there is more than one way of formalizing it, but the perhaps most well-known instance is the difficult open question in the field of complexity theory of whether 𝖯 is equal to 𝖡𝖯𝖯.

A recent line of research could be seen as investigating the reverse direction: to what degree can objects that are random be quickly approximated? Before answering this question, we need to define what we understand by random. The answer is provided by the research field of information theory that deals with questions of compressibility of information, where randomly generated information will be difficult to compress, due to its lack of internal regularities. The subfield of algorithmic randomness, which set out to unify these and other topics and to understand what actually makes a mathematical object random, has produced a wealth of insights into questions about computational properties that random objects must, may, or may not possess. The general pattern in this area is that we put at our disposal algorithmic tools to detect regularities in sequences. Those sequences that are “random enough” to resist these detection mechanisms are then considered random. Many different “resistance levels” have been identified that give rise to randomness notions of different strength. A central and recurring notion that issued from these inquiries is that of Martin-Löf randomness, which is now considered the canonical notion of randomness. A weaker, but still important notion is that of Schnorr randomness. For the rest of the article, we will assume that the reader is familiar with these topics; see, for instance, Downey and Hirschfeldt <cit.> or Nies <cit.> for comprehensive overviews.

With a randomness paradigm in place, one can then study the interactions between randomness and computation speeds. We will focus on a class of objects that can be approximated by an algorithm, and will be interested in the possible speeds of these approximations.

	Let x be a real number. For a fixed sequence (x_n)_n of real numbers converging to it from below, write ρ(n) for the quantity
	x_n+1 - x_n/x - x_n
	for each n ∈, and call (ρ(n))_n the speed quotients of (x_n)_n.


	If there exists a left-approximation of x, that is, a computable increasing sequence of rational number converging to x, then we call x left-computable. If there even exists a left-approximation (x_n)_n with speed quotients (ρ(n))_n such that ρ:=lim sup_n→∞ρ(n) > 0, then we call x speedable.

The notion of speedability was introduced by Merkle and Titov. They made the interesting observation that speedability is incompatible with Martin-Löf randomness <cit.> and asked the question whether the converse holds, that is, whether there exist left-computable numbers which are neither speedable nor Martin-Löf random. A positive answer would have been an interesting new characterization of Martin-Löf randomness; however, Hölzl and Janicki <cit.> showed that such a characterization does not hold. They also introduced the term benign approximations when referring to subclasses of the left-computable numbers that possess special approximations that are in some sense better behaved than general approximations from below. One example is speedability; another that will play a role in this article is the following.

	A real number x is called regainingly approximable if there exists a computable increasing sequence of rational numbers (x_n)_n converging to x with x - x_n ≤ 2^-n for infinitely many n ∈.

Obviously, every regainingly approximable number is left-computable and every computable number is regainingly approximable, but none of these implications can be reversed by results of Hertling, Hölzl, Janicki <cit.>.

Merkle and Titov also showed that the property of being speedable does not depend on the choice of ρ, that is, if some left-computable number is speedable via some ρ witnessed by some left-approximation, it is also speedable via any other ρ' < 1 witnessed by some other left-approximation. However, their proof is highly nonuniform, which led to Barmpalias <cit.> asking whether every such number also has a single left-approximation with lim sup_n→∞ρ(n) = 1. 

We answer this question negatively in this article by showing that the requirement to achieve lim sup_n→∞ρ(n) = 1 is a strictly stronger condition that defines a strict subset of the speedable numbers which we will call superspeedable. We then show that the regainingly approximable numbers are strictly contained in this subset. Thus within the speedable numbers there is a strict hierarchy of notions of benign approximations, namely computable implies regainingly approximable implies superspeedable implies speedable.

Wu <cit.> called finite sums of binary expansions of computably enumerable sets regular reals. We show that these reals are a strict subset of the superspeedable numbers as well; in particular every binary expansion of a computably enumerable set is superspeedable. 
Then we show that finite sums of left-computable numbers can only be superspeedable if at least one of their summands is superspeedable.

With this new approximation notion identified and situated in the hierarchy of benign approximability, it is then natural to wonder how it interacts with randomness. We will show that unlike the Martin-Löf randoms, which by the result of Merkle and Titov <cit.> cannot even be speedable, the Schnorr randoms may even be superspeedable; however they cannot be regainingly approximable.





§ PRELIMINARIES


For any set A ⊆, we denote the complement of A by A̅. For every infinite set A ⊆, there is a unique increasing function p_A → with p_A() = A. For any set A ⊆, we define the real number x_A := ∑_n ∈ A 2^-(n+1)∈[0, 1]. Clearly, A is computable if and only if x_A is computable. If A is only assumed to be computably enumerable, then x_A is a left-computable number; the converse is not true as pointed out by Jockusch (see Soare <cit.>). Thus a real number x ∈[0,1] is called strongly left-computable if there exists a computably enumerable set A ⊆ with x_A = x.

We first observe that, as an alternative to the definition above, speedability could also be defined using two other forms of speed quotients; this will prove useful in the following.

	Let x ∈. For an increasing sequence of rational numbers (x_n)_n converging to x with speed quotients (ρ(n))_n the following statements are easily seen to be equivalent:
	
		
  * lim sup_n→∞ρ(n) > 0, that is, (x_n)_n witnesses the speedability of x;
	
		
  * lim sup_n→∞x_n+1 - x_n/x - x_n+1 > 0;
		
			
  * lim inf_n→∞x - x_n+1/x - x_n < 1.





§ SPEEDABILITY VERSUS IMMUNITY


Merkle and Titov <cit.> showed that all non-high and all strongly left-computable numbers are speedable. On the other hand they established that  Martin-Löf randoms cannot be speedable. In this section we will show that a left-computable number which is not immune has to be speedable. Recall that an infinite set A ⊆ is immune if it does not have a computably enumerable infinite subset. This is equivalent to not having a computable infinite subset.  We say that a real number x ∈[0,1] is immune if there exists an immune set A ⊆ with x_A = x.


	Every left-computable number that is not immune is speedable.


Before we give the proof we mention that left-computable numbers 

	
  * whose binary expansion is not biimmune or
	
  * whose binary expansion is of the form A ⊕ A

can be shown to be speedable by similar arguments as below.
	
Let x be a left-computable real that is not immune. If it is computable, the theorem holds trivially, thus assume otherwise. Let A be such that x = x_A; then there exists a computable increasing function h → with h() ⊆ A. Let (B[n])_n be a computable sequence of finite sets of natural numbers such that the sequence (x_B[n])_n is increasing and converges to x_A. Define the function r → recursively via
		
    r(0) := 0,   
    		r(n+1) := min{m > r(n)  {h(0), …, h(n) }⊆ B[m] }.

It is easy to see that r is well-defined, computable, and increasing.
	Let 
	
    s(n) := min{m ∈   m ∈ B[r(n+1)] ∖ B[r(n)] }

	for all n ∈. Clearly, the sequence (s_n)_n is well-defined and tends to infinity. Finally, define the sequence (C[n])_n via
		
    C[0] := ∅,    C[n+1] := B[r(n+1)]  (s_n + 1),

	for all n∈. Clearly, (C[n])_n is a computable sequence of finite sets of natural numbers, which converge pointwise to A, and the sequence (x_C[n])_n is increasing and converges to x. 

We claim that there are infinitely many n such that s(n) < h(n); this is because otherwise, for almost all n, the sets B[r(n)], B[r(n+1)], … would all mutually agree on their first h(n)-1 bits, hence their limit A would be computable, contrary to our assumption. Thus, fix one of the infinitely many n with s(n) < h(n) and let n'≥ n be maximal such that s(n') < h(n). Then the sets B[r(n'+1)], B[r(n'+2)], … all contain h(n) and, by definition of s and n', agree mutually on their first (h(n)-1) bits; in other words, they even agree on their first h(n) bits.  But by choice of n', these sets also agree with the sets C[n'+1], C[n'+2], …, respectively, on their first h(n) bits; thus these latter sets must also contain h(n) and agree mutually on their first h(n) bits. By definition, the set C[n'] does not contain h(n); thus, in summary, we have
x_C[n'+1] - x_C[n']≥ 2^-h(n) and x - x_C[n'+1]≤ 2^-h(n), hence
x_C[n'+1] - x_C[n']/x - x_C[n'+1]≥ 1.

Since there are infinitely many such n and corresponding n', the left-approximation (x_C[n])_n of x witnesses that x is speedable.




§ SUPERSPEEDABILITY


We now strengthen the conditions in Proposition <ref> to obtain the following new definition.

	Let x ∈. For an increasing sequence (x_n)_n converging to x with speed quotients (ρ(n))_n the following statements are easily seen to be equivalent: 
	
		
  * lim sup_n→∞ρ(n) = 1;
		
		
		
  * lim sup_n→∞x_n+1 - x_n/x - x_n+1 = ∞;
		
		
  * lim inf_n→∞x - x_n+1/x - x_n = 0.
		
	

We call x superspeedable if it has a left-approximation (x_n)_n with these properties.


 Obviously, every superspeedable number is speedable. Barmpalias <cit.> asked whether the converse is true as well. We give a negative answer with the following theorem and corollary.

	There is a left-computable number that is neither immune nor superspeedable.
 

	Let r→ be the function defined by r(n):=max{ℓ∈   2^ℓ divides  n+1}, that is, the characteristic sequence of r is the member of Baire space with the initial segment
	
    010201030102010401020103…

	
	We construct a number α by approximating its binary expansion A. We will slightly abuse notation and silently identify real numbers with their infinite binary expansions; similarly we identify finite binary sequences σ with the rational numbers 0.σ.

We approximate A in stages where during stage s∈ we define a set A[s] such that the sets A[s] converge pointwise to A. For all s and all n with r(n)=0, let A[s](n)=0; and for all s and all n with r(n)=1, let A[s](n)=1. We refer to all remaining bits as the coding bits.
More precisely, we refer to all bits with r(n)=e+2 as the e-coding bits and we let (c^e_i)_i be the sequence of the positions of all e-coding bits in ascending order.
	
	If b=c^e_i for some e and i, then we say that position b is threatened at stage s if A[s](b)=0 and A[s] c^e_i+1 = B_e[s]  c^e_i+1, where (B_0[s])_s, (B_1[s])_s, … is some fixed uniformly effective enumeration of all left-computable approximations.	

	
	[Construction]
		At every stage s, if there exists a least coding bit b ≤ s that is threatened, then set A[s+1](b)=1 and A[s+1](c)=0 for all coding bits c>b. For all other n∈, leave bit n  unchanged, that is, A[s+1](n)=A[s](n).
	 
	

	
[Verification] 
		By construction, once a coding bit has been set to 1, it can only be set back to 0 if a coding bit at an earlier position is set from 0 to 1. From this it follows by an obvious inductive argument that A[s] converges to some limit A in a left-computable fashion; that is, interpreted as real numbers, the values A[0], A[1], … are nondecreasing. Thus α is left-computable.
	
	The A we are constructing is trivially not immune. All that remains to show is that it is not superspeedable.  To that end, fix any e and assume that that the left-computable approximation (B_e[s])_s converges to A; as otherwise there is nothing to prove for e. We will show that this left-computable approximation  does not witness superspeedability of A. 
 
	
	
There are stages s_0 < s_1 < … such that for all i≥ 0, at stage s_i,  
the coding bit b_i=c^e_i is threatened for the last time and is the least coding bit that is threatened at this stage, and such that A has already converged at this stage up to its (b_i+4)-th bit; that is, for all ℓ≥ 1 we have A[s_i]  (b_i+4) = A[s_i+ℓ]  (b_i+4) = A  (b_i+4).
	

Fix some e-coding bit b_i=c^e_i. By the discussion preceding the claim, there is some least stage s such that set A has already converged up to its b_i-th bit. By construction, it must hold that A[s](b_i)=0 and
since the left-approximation (B_e[s])_s converges to A, there must be a stage s'>s at which b_i becomes threatened and is the least threatened coding bit. Thus, during stage s', the bit A(b_i) is set permanently to 1 and, because the two bits following b_i are no coding bits, A has now converged up to its (b_i+4)-th bit.  

Therefore, it suffices to set s_i=s' and to observe that we have s_i < s_i+1 for all i because e-coding bit c^e_i+1 is set to 0 at stage s_i, hence is threatened again after stage s_i.

Let s_0, s_1, … be the stages from the last claim.

There is an ρ_e<1 only depending on e such that for all i and s ∈{s_i,  …, s_i+1-1},

    B_e[s+1]-B_e[s]/A-B_e[s]≤ρ_e .



Fix some i and some stage s as above. Let b=c^e_i and let b'=c^e_i+1. Then A has already converged up to its b-th bit at stage s_i and by definition of a threat we must have B_e[s_i] b =A[s_i] b. But the left-approximation (B_e[s])_s converges to A, hence can never “overshoot” A and thus at stage s_i has already converged up to its b-th bit as well. Consequently, we have B_e[s+1]-B_e[s]≤ 2^-(b-1). 

By construction and our assumptions,

	
  * at stage s_i+1 we set bit b' is set from 0 to 1,
	
  * bit b'+1 permanently maintains value 0, and,
	
  * by definition of a threat, A[s_i+1] and B_e[s_i+1] agree on their first b'+2 < c^e_i+2 many bits.

This implies that

    A-B_e[s+1] 
    ≥ A[s_i+1+1] - B_e[s_i+1] 
    ≥ 2^-(b'+1) = 2^-(b + 2^e+3 + 1),

and in summary we have 
		
    B_e[s+1] - B_e[s]/A - B_e[s]   = B_e[s+1] - 	B_e[s]/(A - B_e[s+1])+(B_e[s+1] - B_e[s])
       
    ≤2^-(b-1)/2^-(b + 2^e+3 + 1)+2^-(b-1)≤ 2^2+2^e+3/1 + 2^2+2^e+3<1,
	

hence there is a constant ρ_e<1 as claimed.

Since e was arbitrary such that (B_e[s])_s converges to A, there cannot be a left-approximation that witnesses superspeedability of A.




By Theorem <ref>, the number α constructed in Theorem <ref> is speedable. 


	There exists a speedable number which is not superspeedable.

Thus, superspeedability is strictly stronger than speedability; we now proceed to identify interesting classes of numbers that have this property. We begin with the class of regainingly approximable numbers. It was shown by Hölzl and Janicki <cit.> that regainingly approximable numbers are speedable. This result can be strengthened; to show that regainingly approximable numbers are in fact superspeedable, we will use the following characterization.




	For a left-computable number x the following are equivalent:
	
		
  * x is regainingly approximable.
		
  * For every computable unbounded function f → there exists a computable increasing sequence of rational numbers (x_n)_n converging to x with
		x - x_n ≤ 2^-f(n)
		for infinitely many n ∈.
	




	Every regainingly approximable number is superspeedable.





	Let x be a regainingly approximable number, and fix a computable increasing sequence (x_n)_n of rational numbers that converges to x and satisfies x - x_n ≤1/(n+1)! for infinitely many n ∈. Define the sequence (y_n)_n with y_n := x_n - 1/n! for all n ∈. Surely, this sequence is computable, increasing and converges to x as well. Considering any of the n ∈ with x - x_n ≤1/(n+1)!, we obtain
	
    y_n+1 - y_n/x - y_n 
    		= (x_n+1 - x_n) + 1/n! - 1/(n+1)!/(x - x_n) + 1/n! 
    		> 1/n! - 1/(n+1)!/1/n! + 1/(n+1)!
    		= n/(n+1)!/n+2/(n+1)! = n/n+2.

	Thus we have lim sup_n→∞y_n+1 - y_n/x - y_n = 1. Therefore, x is superspeedable.


The next class of numbers that we investigate is the following. 

	A real number is called regular if it can be written as a finite sum of strongly left-computable numbers.

Note that this includes in particular all binary expansions of c.e. sets. Using the following helpful definition and propositions, we now show that every regular number is superspeedable.

	Let f → be a function which tends to infinity. Then the function u_f → is defined by u_f(n) := |{k∈  f(k) = n}| for all n ∈. 

Note that u_f possesses a computable approximation from below, namely 
u_f[0](n) := 0 and 
	
    u_f[t+1](n) := 
    		
    			u_f[t](n) + 1    if f(t) = n,
    
    			u_f[t](n)    otherwise,

for all n,t ∈.

	A real number x is regular if and only if there exists a computable function f → with ∑_k=0^∞ 2^-f(k) = x, a so-called name of f, such that u_f is bounded.

	Every regular number is superspeedable; in particular this holds for every strongly left-computable number. 


	Let x be a regular number. Fix some computable name f → for x and some constant c ∈ with u_f(n) ≤ c for all n ∈. We define two sequences of natural numbers (a_n)_n and (b_n)_n and a sequence of sets of natural numbers (I_n)_n by
		
    a_n := n(n+1)/2,    b_n := a_n + n = a_n+1 - 1,    I_n := {a_n, …, b_n},

	for all n ∈. It is easy to verify that the set {I_n   n ∈} is a partition of  and that we also have |I_n| = n+1 for all n ∈.
	
	We call a stage s∈ a true stage if we have f(s) < f(t) for all t > s. Since f tends to infinity, there are infinitely many true stages. For any n, s ∈, we say that the interval I_n is incomplete at stage s if there exists some stage t > s with f(t) ∈ I_n. Otherwise, we say that I_n is complete at s. Since f tends to infinity, every interval is complete at some stage. Therefore, we can define the sequence (θ_n)_n with
	θ_n := min{t ∈  I_n  is complete at stage  t }
	for all n ∈. In order to show that x is superspeedable, we consider several cases:
	
		
  * Suppose that there are infinitely many n ∈ with f() ∩ I_n = ∅. Considering such an n with a_n > min_k∈ f(k), let s ∈ be the latest true stage with f(s) < a_n. Then we have ∑_k=s+1^∞ 2^-f(k)≤ c · 2^-b_n, due to f() ∩ I_n = ∅. Then we obtain
		
    2^-f(s)/∑_k=s+1^∞ 2^-f(k) > 2^-a_n/c· 2^-b_n = 2^-a_n/c· 2^-(a_n + n) = 2^n/c.

		As there exist infinitely many n as above, x is superspeedable.
		
  * Otherwise, we can assume w.l.o.g. that f() ∩ I_n ≠∅ for all n ∈.
		
		Suppose that there are infinitely many n ∈ with some stage s ∈ at which I_n is incomplete and I_n+1 is complete. Let t > s be the earliest true stage at which I_1,…,I_n are all complete. On the one hand, we have f(t) < a_n+1. On the other hand we have ∑_k=t+1^∞ 2^-f(k)≤ c · 2^-b_n+1, since, in particular, I_n+1 is complete at stage t. We obtain
		
    2^-f(s)/∑_k=s+1^∞ 2^-f(k)
    			> 2^-a_n+1/c· 2^-b_n+1 
    			= 2^-a_n+1/c· 2^-(a_n+1+n+1) 
    			= 2^n+1/c.

		As there exist infinitely many n as above, x is superspeedable.
		
		
  * Otherwise, we can assume w.l.o.g. that   (θ_n)_n is an increasing sequence. This also implies that θ_n is a true stage for every n ∈. Define the sequence (d_n)_n by d_n := b_n - f(θ_n). Suppose that (d_n)_n is unbounded; then for every n ∈ we have
		
    2^-f(θ_n)/∑_k=θ_n+1^∞ 2^-f(k)
    			= 2^-f(θ_n)/c· 2^-b_n 
    			= 2^b_n - f(θ_n)/c
    			= 2^d_n/c.

		Therefore, x is superspeedable.
		
		
  * Otherwise, (d_n)_n is bounded. Fix some natural number D ≥ 1 with d_n ≤ D for all n ∈. Define the sequences (T_n)_n and (T_n[t])_n,t in {0, …, c}^D as follows:
			
    T_n := (u_f(b_n - D + 1), …, u_f(b_n)),   
    				T_n[t] := (u_f[t](b_n - D + 1), …, u_f[t](b_n))

		Clearly, we have lim_t→∞ T_n[t] = T_n for all n ∈. Fix some D-tuple T ∈{0, …, c}^D satisfying  T_n = T for infinitely many n ∈. Assume w.l.o.g. that there are infinitely many odd numbers n with this property, and recursively define the function s → as follows:
		Let s(0) := 0, and define s(m+1) as the smallest stage t > s(m) such that there is some odd number n ∈ with T_n[t] = T and T_n[t] ≠ T_n[s(m)]. Clearly, s is well-defined, computable and increasing. Finally, define the computable and increasing sequence (x_n)_n by x_n := ∑_k=0^s(n) 2^-f(k) for all n∈; this clearly converges to x. Let n ∈ be an even number with T_n+1 = T. By the previous assumption that (θ_n)_n is increasing, there exists a uniquely determined number m ∈ with s(m+1) = θ_n+1. Similarly, by the definition of s, we have s(m) < θ_n. On the one hand, we have x_m+1 - x_m≥ 2^-b_n. On the other hand, we have x - x_m+1≤ c· 2^-b_n+1. So we finally obtain
		
    x_m+1 - x_m/x - x_m+1≥2^-b_n/c · 2^-b_n+1 
    			= 2^b_n+1-b_n/c 
    			= 2^a_n+1-a_n+1/c 
    			= 2^n+2/c.

		As there exist infinitely many n as above, x is superspeedable.  

As a corollary of the theorem, we obtain that the converse of Theorem <ref> does not hold.

	Not every superspeedable number is regainingly approximable.


	By Theorem <ref>, every strongly left-computable number is superspeedable. However, Hertling, Hölzl, and Janicki <cit.> constructed a strongly left-computable number that is not regainingly approximable. 

Similarly, the converse of Theorem <ref> is not true either, as the following observation shows.

	Not every superspeedable number is regular.


 Hertling, Hölzl, and Janicki <cit.> constructed a regainingly approximable number α such that for infinitely many n it holds that K(α n) > n. By Theorem <ref>, this α is superspeedable. However, it cannot be regular, as it is easy to see that the initial segment Kolmogorov complexities of regular numbers must be logarithmic everywhere.






§ SUPERSPEEDABILITY AND ADDITIVITY


In this section we study the behaviour of superspeedability with regards to additivity. The following lemma will be useful; we omit the easy proof.		

	Let α and β be left-computable numbers, and let (c_n)_n be a computable increasing sequence of rational numbers converging to α + β. Then there exist computable increasing sequences of rational numbers (a_n)_n and (b_n)_n converging to α and β, respectively, with a_n + b_n = c_n for all n ∈.

		
			Let α and β be left-computable numbers such that α + β is superspeedable. Then at least one of α or β must be superspeedable.
		
		
			Suppose that neither α nor β are superspeedable. Let γ := α + β, and let (c_n)_n be a computable increasing sequence of rational numbers converging to γ. We show that there is some constant ρ∈ (0, 1) with c_n+1 - c_n/γ - c_n≤ρ for all n ∈. Due to Lemma <ref>, there exist computable increasing sequences of rational numbers (a_n)_n and (b_n)_n converging to α and β, respectively, with a_n + b_n = c_n for all n ∈. Since α and β are both not superspeedable, there is some constant ρ∈ (0, 1) satisfying both a_n+1 - a_n/α - a_n≤ρ and b_n+1 - b_n/β - b_n≤ρ for all n ∈. Considering some arbitrary n ∈, we obtain
			
    c_n+1 - c_n/γ - c_n   = (a_n+1 - a_n) + (b_n+1 - b_n)/(α - a_n) + (β - b_n) 
    				= a_n+1 - a_n/α - a_n· (α - a_n) + b_n+1 - b_n/β - b_n· (β - b_n) /(α - a_n) + (β - b_n)
       ≤max{a_n+1 - a_n/α - a_n, b_n+1 - b_n/β - b_n}·((α - a_n) + (β - b_n)) /(α - a_n) + (β - b_n)
    
    				≤ρ.

			Thus, γ is not superspeedable either.
		

		
		
		

§ BENIGNNESS VERSUS RANDOMNESS

		
				Recall that Merkle and Titov <cit.> made the observation that  Martin-Löf randomness is incompatible with speedability. In this section, we study the analogous question for the weaker randomness notion of Schnorr randomness.
		We begin with the easy observation that Schnorr randomness is incompatible with the rather demanding benignness notion of regaining approximability; the argument is a straight-forward modification of the result of Merkle and Titov.
		
			No regainingly approximable number can be Schnorr random.
		 
		
			Let x be regainingly approximable, witnessed by its  left-approximation (x_n)_n. Then x is covered by the Solovay test (S_n)_n  where S_n=(x_n-2^-(n-1),x_n+2^-(n-1)) for all n∈. This test is total, that is, the measure of the union of its components is computable; then, by a result of Downey and Griffiths <cit.>, x cannot be Schnorr random.
		
		In light of this result, it is natural to ask how far down into the hierarchy of benignness notions the class of Schnorr randoms reaches. The answer is given by the following theorem.



		
			There exists a superspeedable number which is Schnorr random.
		
		We point out that the number we construct will have the additional property that it is not partial computably random. 
				
		Recall, for instance from Odifreddi <cit.>, that a set A is called dense simple if it is c.e. and p_A̅ dominates every computable function. While the complement of a dense simple set must be very thin by definition, 
		we claim that there does exist such set A whose binary expansion contains arbitrarily long sequences of zeros. 
		To see this, recall that a set B is called maximal if it is c.e. and coinfinite and for any c.e. set C with B⊆ C, we must have that C is cofinite or that C∖ B is finite; in other words, if B only has trivial c.e. supersets. Such sets exist, for instance see Odifreddi <cit.>. If we partition the natural numbers into a sequence (I_n)_n of successive intervals of growing length by letting I_0:={0}, and I_n+1:={max I_n+1,…, max I_n+n+2} for all n∈ and fix some maximal set B,  then it is easy to check that we obtain a set A as required by letting
		
    A:={n ∃ k,ℓ [
    		[                               ∨ (n ∈ I_k ∧ k∈ B)  ∨; (n  is the ℓ-th smallest element of  I_k ∧#(B k)≥ℓ) ]]} .

	
		
			Let A be a set that is dense simple and whose binary expansion contains arbitrarily long sequences of zeros. Define Ω_A bitwise via 
			
    Ω_A(n):=Ω(m)    if  n=p_A(m),
    
    				0    else;

			for all n∈; that is, Ω_A contains all bits of Ω, but at those places that are elements of A; all other bits of Ω_A are zeros. 
			Let (A[t])_t be a computable enumeration of A and for all n∈ write p_A(n)[t] for the n-th smallest element in A[t], if it already exists. Then it is easy to see that
			(Ω_A[t])_t defined bitwise via
			
    Ω_A(n)[t]:=Ω(m)[t]    if  n=p_A(m)[t]↓,
    
    				0    else,

			for all n∈, is a left-approximation of Ω_A; namely, the individual bits of Ω are approximated in a left-computable fashion, and as more and more bits appear in the computable enumeration of A, the positions where the bits of Ω get stored in Ω_A may move to the left.
			
			We claim that Ω_A is as required by the theorem.
			
			
			
				
  * It is easy to see that Ω_A is superspeedable by arguments analogous to those previously used in this article. Namely, recall that A contains arbitrarily long blocks of bits that will permanently maintain value 0, that is, for all n in such a block and all t, we have Ω_A(n)[t]=0. As a consequence, the left-approximation of Ω_A described above witnesses superspeedability at the infinitely many stages where for the last time a bit left of one of these blocks changes.
				
				
  * Note that the fact that A̅ is dense immune implies that for every computable increasing function f →, there exists a number m_f ∈ with |A̅ f(n)| ≤n/4 for all n ≥ m_f.
				
		
  * Let α, ω→ be defined  via
				
    [    α(n)      := min{t ∈    A[t]           (n+1)       =       A           (n+1)      },;    ω(n)      := min{t ∈    Ω[t]           (n/4)       =       Ω           (n/4)       };         ]

				for all n∈. 	We claim that there exists a number m_1 ∈ such that  for every n ≥ m_1 we have
				α(n) ≤ω(n). This is clear since the Kolmogorov complexity of computably enumerable sets grows logarithmically in the length of its initial segments, while that of Ω grows linearly.
				
		
  * Let θ→ be defined  via
		
    θ(n) := min{t ∈ Ω_A[t]  n = Ω_A  n }





		for all n∈. 	We claim that there exists a number m_2 ∈ such that  for every n ≥ m_2 we have
		ω(n) ≤θ(n). To see this, fix some n ≥ m_id and such that Ω_A n contains at least one 1; write t_n for θ(n). 
		
		First, it is easy to see that if we let ℓ_n denote the maximal ℓ such that (Ω_A[t_n] n)(ℓ)=1, then we must already have A[t_n]ℓ_n = Aℓ_n. But then, since we chose n ≥ m_id,  the sets A and A[t_n] contain exactly the same at least ℓ_n - n/4 elements less than ℓ_n. Consequently,  we must have Ω[t_n]  (ℓ_n-n/4) = Ω (ℓ_n-n/4). If we choose m_2 ≥ m_id such that for all n ≥ m_2 we have ℓ_n ≥n/2, we are done. 
		To see that such an m_2 exists, we argue as follows: For a given n≥ m_id,  Ω_A n contains at least the first k ≥3/4· n bits of Ω; and thus if the last 1 in Ω_A n occurs before position n/2, then the last k/3 bits of Ω must be 0. But this can occur only for finitely many k as Ω is Martin-Löf random.
		




		
  * Now we show that Ω_A is not partial computably random. We recursively define the partial martingale d ⊆→_≥ 0 as follows: Let d(λ) := 1, and suppose that d(σ) is defined for some σ∈. Let t_σ∈ be the earliest stage with Ω_A[t_σ] |σ| = σ, if it exists. 

Then define d(σ0) and d(σ1) via
			
    d(σ0) := 3/2· d(σ)    if |σ| ∉ A[t_σ],
    
    				d(σ)    otherwise,    
    			d(σ1) := 1/2· d(σ)    if |σ| ∉ A[t_σ],
    
    				d(σ)    otherwise.

		It is clear that d is a partial computable martingale. 
		We claim that d succeeds on Ω_A. To see this, let ℓ≥max(m_id, m_1, m_2) and assume that d receives input σ := Ω_A ℓ. Let t_σ∈ be the first stage such that Ω_A [t_σ] ℓ = σ. Then, by choice of ℓ and σ, we have α(ℓ) ≤ω(ℓ) ≤θ(ℓ) =t_σ, thus A[t_σ]  (ℓ + 1) = A  (ℓ + 1). Thus,  ℓ∉A[t_σ] if and only if ℓ∉A, and by construction, for each of the infinitely many ℓ∉A, we have d(Ω_A(ℓ+1)) = 3/2· d(σ). On the other hand, for all other ℓ, we have d(Ω_A(ℓ+1)) = d(σ). Thus, lim_n→∞ d(Ω_A n) = ∞, and Ω_A is not partial computably random.
				
				
  * It remains to show that Ω_A is Schnorr random. For the sake of a contradiction, assume this is not the case; then, according to a result of Franklin and Stephan <cit.>, there exists a computable martingale d →_≥ 0 and a computable increasing function f → with d(Ω_A  f(n)) ≥ 2^n for infinitely many n ∈. W.l.o.g. we can assume d(λ) = 1.
				
				Let m:=max(m_f, m_1) and define the partial computable martingale d' ⊆→_≥ 0 recursively as follows: Let d'(σ) := 1 for each σ with |σ|≤ m. Now suppose that d'(σ) is defined for some σ∈, write ℓ := |σ|, and let t_σ∈ be the earliest stage with Ω[t_σ] ℓ = σ, if it exists. To define how d' bets on the next bit, imitate the betting of d on the p_A[t_σ](ℓ+1)-th bit of Ω_A[t_σ]. It is clear that d' is computable.
								
				We claim that d' succeeds on Ω.	To see this, fix any ℓ≥ m and assume that d' receives input σ := Ωℓ.
				Let t_σ∈ be the first stage such that Ω [t_σ] ℓ = σ. By choice of m, this implies 

p_A[t_σ](ℓ+1) = p_A(ℓ+1). By construction, d' bets in the same way on Ω (ℓ+1) as d does on Ω_A  p_A(ℓ+1).
				
				Define the function g → by g(n) := f(n) - |A̅ f(n)|, and pick any of the, by assumption, infinitely many n with d(Ω_A  f(n)) ≥ 2^n.
				Recall that Ω_A  f(n) contains at most n/4 bits which belong to A̅ and each of them can at most double the starting capital. 
				This implies that d', which omits exactly these bets but imitates all the others, must still  at least achieve capital 2^3/4· n on the initial segment Ω g(n). This contradicts the well-known fact that Ω is partial computably random.
				
			
		
		

§ FUTURE RESEARCH

		
		We finish the article by highlighting possible future research directions:
		
		The first two open questions concern the positions marked 0.55[unclear/.style = draw=black,thick,circle, densely dashed, inner sep=0.12cm,node contents=]
				 at (0,0) [unclear];
		_ 1 and 0.55[unclear/.style = draw=black,thick,circle, densely dashed, inner sep=0.12cm,node contents=]
		 at (0,0) [unclear];
	_ 2 in Figure <ref>; in both cases it is unknown whether any such numbers can exist. Note that proving the existence of 0.55[unclear/.style = draw=black,thick,circle, densely dashed, inner sep=0.12cm,node contents=]
	 at (0,0) [unclear];
_ 1 would give a negative answer to the open question posed by Hölzl and Janicki <cit.> whether the left-computable numbers are covered by the union of the Martin-Löf randoms with the speedable and the nearly computable numbers; in particular, it would provide an alternative way to obtain a counterexample to the question of Merkle and Titov discussed in the introduction. 
Concerning 0.55[unclear/.style = draw=black,thick,circle, densely dashed, inner sep=0.12cm,node contents=]
		 at (0,0) [unclear];
_ 2, one might be tempted to believe that such a number could be constructed by an argument similar to that used to prove Theorem <ref> but using a maximal c.e. set A; such a set would still be dense simple by a result of Martin <cit.>, but it would only contain isolated zeros. However, it can be shown that an Ω_A constructed in this way would still end up being superspeedable.



			
			
			Next, besides Schnorr randomness, there are numerous other randomness notions weaker than Martin-Löf randomness, such as computable randomness or weak s-randomness (see, for instance, Downey and Hirschfeldt <cit.>). It is a natural to ask which of them are compatible with which of the notions of benign approximability discussed in this article.
			
			Finally, in this field, many relevant properties of the involved objects are not computable; one might ask how far
			from computable they are. One framework in which questions of this type can be studied is the Weihrauch degrees, a tool to gauge the computational difficulty of mathematical tasks by thinking of them as black boxes that are given  instances of a problem and that have find one of its admissible solutions. This model then allows comparing the “computational power” of such black boxes with each other (for more details see, for instance, the survey by Brattka, Gherardi, and Pauly <cit.>). In the context of this article, we could for example ask for the Weihrauch degrees of the following non-computable tasks, with many variants imaginable:
			
				
  * Given an approximation that witnesses speedability of some number as well as a desired constant, determine the stages at which the speed quotients of the given approximation beat the constant.				

				
  * For a speedable number, given an approximation to it as well as a desired speed constant ρ, determine another approximation of that number which achieves speed constant ρ in the limit superior.
				
  * For an approximation witnessing regaining approximability of some number, determine the sequence of n's at which the approximation “catches up.”
			
		
		

		



§ APPENDIX



	Given two computable increasing sequences of rational numbers (d_n)_n and (e_n)_n converging to α and β, respectively, fix N ∈ with 
	
    -N < min{d_0, e_0}  and  -2N < c_0,
 
	and define a_-1 := b_-1 := -N and c_-1 := -2N. We will inductively define an increasing function s → as well as the desired sequences (a_n)_n and (b_n)_n.
	
	For every n ∈, define s(n) such that the inequalities
	
    d_s(n) > a_n-1,   e_s(n) > b_n-1,   d_s(n) + e_s(n)≥ c_n

	are satisfied; this is obviously always possible. Assume by induction that a_n-1 + b_n-1 = c_n-1. Note that the quantities d_s(n) - a_n-1 and e_s(n) - b_n-1 and c_n - c_n-1 are positive rational numbers. Thus there exist natural numbers p_a, p_b, q ≥ 1 and p_c ≥ 2 with
	
    d_s(n) - a_n-1 = p_a/q,   
    		e_s(n) - b_n-1 = p_b/q,  
    		c_n - c_n-1 = p_c/q.
	
	This implies
	
    p_a/q + p_b/q
    		= (d_s(n) + e_s(n)) - (a_n-1 + b_n-1)
    		≥ c_n - c_n-1
    		= p_c/q,

	hence p_a + p_b ≥ p_c. 
	Let m := min{p_a, p_c - 1}, and finally define a_n := a_n-1 + m/q and b_n := b_n-1 + p_c-m/q. It is easy to verify that (a_n)_n and (b_n)_n are both computable and increasing sequences, converge to α and β, respectively, and satisfy a_n + b_n = c_n for all n ∈.

