Solovay Reducibility and Speedability Outside of left-c.e. Reals

A real number is left-c.e. if it has a left-c.e. approximation, i.e., a computable nondecreasing sequence a0, a1, ... of rationals that converges to the real number. Furthermore, a real number α is Solovay reducible to a real number β if there exists a partially computable function g that maps every rational number q < β to some rational number g(q) < α such that, for some real constant c and all q < β, it holds that α − g(q) < c(β − q).

Solovay reducibility can be used to compare the speed at which left-c.e. numbers can be approximated: if a real number α is Solovay reducible to a left-c.e. real number β, then also α is left-c.e. and, for every left-c.e. approximation of β, there is a left-c.e. approximation of α that converges at least as fast up to a constant factor.

Among the left-c.e. reals, the Martin-Löf random ones have been intensively studied, and it is known that they have several natural equivalent characterizations. For example, by results of Solovay and of Calude, Hertling, Khoussainov and Wang, the Martin-Löf random left-c.e. reals are exactly the halting probabilities of universal Turing machines. Furthermore, Kŭcera and Slaman demonstrated that, within the left-c.e. reals, the Martin-Löf random ones form a highest degree of Solovay reducibility, i.e., a left-c.e. real β is Martin-Löf random if and only if every left-c.e. real α is reducible to β. In fact, they showed that the latter holds via arbitrary left-c.e. approximations of α and β. As a consequence, given any Martin-Löf random left-c.e. reals α and β, they are mutually Solovay reducible to each other via arbitrary left-c.e. approximations a0, a1, . . . and b0, b1, . . . of α and β, respectively, hence, there are reals c > 0 and d such that, for all n, it holds that c < (α − an) / (β − bn) < d. (1)

Actually more is known: the considered ratios are not only restricted to the interval (c, d) but, by a celebrated theorem of Barmpalias and Lewis-Pye, they converge, i.e., the limit lim n→∞ (α − an) / (β − bn), exists and does not depend on the choice of the left-c.e. approximations of α and β. A left-c.e. real α is ρ-speedable if it has a left-c.e. approximation a0, a1, . . . such that, for some computable function f , it holds that lim inf n→∞ (α − af (n)) / (α − an) = ρ, and a left-c.e. real is speedable if it is ρ-speedable for some ρ < 1. Merkle and Titov introduced these notions and observed that, by the theorem of Barmpalias and Lewis-Pye, it is immediate that Martin-Löf random left-c.e. reals cannot be speedable, furthermore, they gave a short direct proof of the latter fact.

Solovay reducibility is a standard tool for investigating the class of left-c.e. reals. However, though defined as a binary relation on the set of all reals, Solovay reducibility is only rarely used outside the realm of left-c.e. reals, in fact, is viewed as “badly behaved” there in general. The main theme of this thesis is that, when investigating all reals, Solovay reducibility should be replaced by monotone Solovay reducibility. The latter reducibility is defined literally the same as Solovay reducibility except that, in addition, it is required that the function g in (1) is nondecreasing, i.e., that g(q) ≤ g(q′) holds for all q and q′ in the domain of g, where q < q′. Essentially all results that are shown in what follows suggest that monotone Solovay reducibility should be used when investigating all and not just left-c.e. reals.

First, monotone Solovay reducibility can indeed be considered as an extension of Solovay reducibility since both relations coincide on the set of left-c.e. reals. Monotone Solovay reducibility is a reflexive and transitive relation, hence, induces a degree structure in the usual way. Furthermore, the classes of computable, of left-c.e., of right-c.e., of d.c.e. and of computably approximable, or ∆02, reals are all closed downwards under monotone Solovay reducibility.

Second, when extending the notion of speedability from the left-c.e. to all reals, this is done in terms of monotone Solovay reducibility of a real to itself. The resulting notion of speedability coincides on the set of left-c.e. reals with the notion of speedability for left-c.e. reals that has been previously defined in terms of left-c.e. approximations, whereas a definition in terms of Solovay reducibility would be trivial in so far as it renders all left-c.e. reals speedable.

For the speedability notion defined for left-c.e. reals in terms of left-c.e. approximations, the following is shown. The notion is robust in so far as a real that is ρ-speedable for some ρ < 1 is actually ρ-speedable for all ρ > 0 via any left-c.e. approximation of the real. Also speedability is a degree property, i.e., in a Solovay degree, either every or no real is speedable. Furthermore, Martin-Löf random left-c.e. reals are never speedable, while all nonhigh left-c.e. reals are speedable. For speedability defined in terms of monotone Solovay reducibility, some of these results extend to all reals, in particular, robustness with respect to the choice of nonzero ρ and the nonspeedability of Martin-Löf random reals. Being Martin-Löf random is not equivalent to being nonspeedable, neither for all reals nor when restricting attention to the left-c.e. reals. The former result is shown below by constructing a right-c.e. counterexample, i.e., a right-c.e. real that is neither Martin-Löf random nor speedable. The latter, more interesting and more difficult result is due to Hölzl and Janicki, who constructed a left-c.e. counterexample.

Third, the theorem of Barmpalias and Lewis-Pye allows an equivalent reformulation in terms of monotone Solovay reducibility, which can be extended to all reals. This extension is one of the main results of this thesis. A corresponding reformulation in terms of Solovay reducibility is false in general and is actually false for all left-c.e. reals.