German Title: Solovay-Reduzierbarkeit und Beschleunigbarkeit außerhalb von linksberechenbaren Zahlen

Preview

PDF, English - main document Download (700kB) | Terms of use

Abstract

A real number is left-c.e.\ if it has a left-c.e.\ approximation, i.e., a computable nondecreasing sequence $a_0, a_1, ...$ of rationals that converges to the real number. Furthermore, a real number $\alpha$ is Solovay reducible to a real number $\beta$ if there exists a partially computable function~$g$ that maps every rational number~$q<\beta$ to some rational number~$g(q)<\alpha$ such that, for some real constant~$c$ and all~$q < \beta$, it holds that \[ \alpha - g(q) < c (\beta - q) . \] Solovay reducibility can be used to compare the speed at which left-c.e.\ numbers can be approximated: if a real number~$\alpha$ is Solovay reducible to a left-c.e.\ real number~$\beta$, then also~$\alpha$ is left-c.e.\ and, for every left-c.e.\ approximation of~$\beta$, there is a left-c.e.\ approximation of~$\alpha$ 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~\cite{1975} and of Calude, Hertling, Khoussainov and Wang~\cite{Calude-Hertling-Khoussainov-Wang}, the Martin-Löf random left-c.e.\ reals are exactly the halting probabilities of universal Turing machines. Furthermore, Kučera and Slaman~\cite{Kucera-Slaman-2001} 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~$\beta$ is Martin-Löf random if and only if every left-c.e.\ real~$\alpha$ is reducible to~$\beta$. In fact, they showed that the latter holds via arbitrary left-c.e.\ approximations of~$\alpha$ and~$\beta$. As a consequence, given any Martin-Löf random left-c.e.\ reals~$\alpha$ and~$\beta$, they are mutually Solovay reducible to each other via arbitrary left-c.e.\ approximations~$a_0, a_1, \ldots$ and~$b_0, b_1, \ldots$ of~$\alpha$ and~$\beta$, respectively, hence, there are reals $c>0$ and $d$ such that, for all~$n$, it holds that \begin{equation}\label{eq:abstract-solovay-constant} c<\frac{\alpha - a_n}{\beta - b_n}<d. \end{equation} 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~\cite{Barmpalias-Lewispye-2017}, they converge, i.e., the limit \[%begin{equation}\label{eq:BLP-abstract} \lim_{n\to\infty}\frac{\alpha - a_n}{\beta - b_n}, \]%end{equation} exists and does not depend on the choice of the left-c.e.\ approximations of~$\alpha$ and~$\beta$.

A left-c.e.\ real~$\alpha$ is $\rho$-speedable if it has a left-c.e.\ approximation~$a_0, a_1, \ldots$ such that, for some computable function~$f$, it holds that \[ \liminf\limits_{n\to\infty}\frac{\alpha-a_{f(n)}}{\alpha-a_n} = \rho, \] and a left-c.e.\ real is speedable if it is $\rho$-speedable for some~$\rho < 1$. Merkle and Titov~\cite{Merkle-Titov-2020-ccr} 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 \say{badly behaved} there in general~\cite[Section~9.1]{Downey-Hirschfeldt-2010}. 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~\eqref{eq:abstract-solovay-constant} is nondecreasing, i.e., that~$g(q) \le 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~$\Delta^0_2$, 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 $\rho$-speedable for some~$\rho< 1$ is actually $\rho$-speedable for all~$\rho>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~$\rho$ 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~\cite{Hoelzl-Janicki-2023}, 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.

Translation of abstract (German)

Eine reelle Zahl ist linksberechenbar, wenn sie eine linksberechenbare Approximation besitzt, dass heißt, es gibt eine berechenbare nichtfallende Folge~$a_0, a_1, \ldots$ von rationalen Zahlen, die gegen die reelle Zahl konvergiert. Weiter ist eine reelle Zahl $\alpha$ auf eine reelle Zahl~$\beta$ Solovay-reduzierbar, wenn es eine partiell berechenbare Funktion~$g$ gibt, die jede rationale Zahl $q<\beta$ auf eine rationale Zahl~$g(q)<\alpha$ abbildet, so dass für eine reelle Konstante $c$ und alle~$q < \beta$ gilt \[ \alpha - g(q) < c (\beta - q) . \] Mittels der Solovay-Reduzierbarkeit kann die Geschwindigkeit verglichen werden, mit der linksberechenbare Zahlen approximiert werden können. Falls eine reelle Zahl~$\alpha$ Solovay-reduzierbar auf eine linksberechenbare reelle Zahl~$\beta$ ist, dann ist~$\alpha$ ebenfalls linksberechenbar und gibt es für jede linksberechenbare Approximation von~$\beta$ eine linksberechenbare Approximation von~$\alpha$, die bis auf einen konstanten Faktor mindestens genauso schnell konvergiert.

Unter den linksberechenbaren reellen Zahlen wurden die Martin-Löf-zufälligen intensiv erforscht und es ist bekannt, dass diese verschiedene natürliche äquivalente Charakteris\-ier\-ungen erlauben. Zum Beispiel sind nach Ergebnissen von Solovay~\cite{1975} und von Calude, Hertling, Khoussainov und Wang~\cite{Calude-Hertling-Khoussainov-Wang} die Martin-Löf-zufälligen linksberechenbaren reellen Zahlen genau die Haltewahrscheinlichkeiten universeller Turingmaschinen. Kučera und Slaman~\cite{Kucera-Slaman-2001} konnten zeigen, dass innerhalb der linksberechenbaren reellen Zahlen die Martin-Löf-zufälligen Zahlen einen höchsten Grad der Solovay-Reduzierbarkeit bilden, das heißt, eine linksberechenbare reelle Zahl~$\beta$ ist genau dann Martin-Löf-zufällig, wenn jede linksberechenbare reelle Zahl~$\alpha$ auf~$\beta$ reduzierbar ist, und dass letztere Aussage sogar bezüglich beliebiger linksberechenbarer Approximationen von~$\alpha$ und~$\beta$ gilt.

Folglich sind beliebige Martin-Löf-zufällige linksberechenbare reelle Zahlen~$\alpha$ und~$\beta$ bezüglich beliebiger linksberechenbarer Approximationen~$a_0, a_1, \ldots$ und~$b_0, b_1, \ldots$ von~$\alpha$ beziehungsweise~$\beta$ gegenseitig Solovay-reduzierbar, das heißt, es gibt reelle Zahlen~$c>0$ und~$d$, so dass für alle~$n$ gilt \begin{equation}\label{eq:abstract-solovay-constant:de} c<\frac{\alpha - a_n}{\beta - b_n}<d. \end{equation} Tatsächlich ist weit mehr bekannt, als dass die Werte der hier betrachteten Brüche in einem Intervall~$(c,d)$ liegen: nach einem bekannten Satz von Barmpalias und Lewis-Pye~\cite{Barmpalias-Lewispye-2017} konvergieren die Werte sogar: der Grenzwert \[%begin{equation}\label{eq:BLP-abstract} \lim_{n\to\infty}\frac{\alpha - a_n}{\beta - b_n} \]%end{equation} existiert und hängt nicht von der Wahl der Linksapproximationen von~$\alpha$ und~$\beta$ ab.

Eine linksberechenbare reelle Zahl~$\alpha$ ist $\rho$-be\-schleu\-nigbar, falls sie eine Linksapproximation~$a_0, a_1, \ldots$ besitzt, so dass für eine berechenbare Funktion~$f$ gilt \[ \liminf\limits_{n\to\infty}\frac{\alpha-a_{f(n)}}{\alpha-a_n} \le \rho, \] und sie ist beschleunigbar, falls sie $\rho$-be\-schleu\-nigbar für ein~$\rho < 1$ ist. Merkle and Titov~\cite{Merkle-Titov-2020-ccr} führten diese Begriffe ein und beobachteten, dass aus dem Satz von Barmpalias and Lewis-Pye sofort folgt, dass Martin-Löf-zufällige linksberechenbare reelle Zahlen nicht beschleunigbar sein können, zusätzlich gaben sie einen kurzen direkten Beweis dieser Tatsache an.

Die Solovay-Reduzierbarkeit ist ein Standardwerkzeug zur Untersuchung der Klasse der linksberechenbaren reellen Zahlen. Obwohl die Solovay-Reduzierbarkeit als binäre Relation auf der Menge aller reellen Zahlen definiert ist, wird sie nur selten außerhalb des Bereichs der reellen Zahlen verwendet und wird dort sogar als im Allgemeinen "badly behaved" angesehen~[5, Abschnitt 9.1]. Die zentrale These dieser Arbeit ist, dass bei der Untersuchung aller reellen Zahlen die Solovay-Reduzierbarkeit durch die monotone Solovay-Reduzierbarkeit ersetzt werden sollte. Letztere Reduzierbarkeit ist wörtlich genauso definiert wie die Solovay-Reduzier\-bar\-keit, außer dass zusätzlich verlangt wird, dass die Funktion~$g$ in~\eqref{eq:abstract-solovay-constant:de} monoton steigend ist, das heißt, es gilt~$g(q) \le g(q')$ für alle~$q$ und~$q'$ im Definitionsbereich von~$g$ mit~$q < q'$. Im Wesentlichen alle im Folgenden gezeigten Ergebnisse legen nahe, dass die monotone Solovay-Reduzierbarkeit verwendet werden sollte, wenn alle und nicht nur die linksberechenbaren reelle Zahlen untersucht werden.

Erstens kann die monotone Solovay-Reduzierbarkeit als eine Erweiterung der Solovay-Reduzier\-bar\-keit betrachtet werden, da beide Relationen auf der Menge der linksberechenbaren reellen Zahlen übereinstimmen. Die monotone Solovay-Reduzierbarkeit ist eine reflexive und transitive Relation und induziert daher in der üblichen Weise eine Gradstruktur. Darüber hinaus sind die Klassen der berechenbaren, der linksberechenbaren, der rechtsberechenbaren, der d.c.e.\ und der berechenbar approximierbaren, oder~$\Delta^0_2$, reellen Zahlen alle unter der monotonen Solovay-Reduzierbarkeit nach unten abgeschlossen.

Zweitens wird die Erweiterung des Begriffs der Beschleunigbarkeit von den linksberechenbaren auf alle reellen Zahlen mittels der monotonen Solovay-Reduzierbarkeit als geeignete Reduktion einer reellen Zahl auf sich selbst definiert. Der resultierende Begriff der Beschleunigbarkeit stimmt auf der Menge der linksberechenbaren reellen Zahlen mit dem Begriff der Beschleunigbarkeit für linksberechenbare reelle Zahlen überein, der zuvor mittels linksberechenbarer Approximationen definiert wurde, wohingegen eine Definition mittels Solovay-Reduzierbarkeit insofern trivial wäre, als für letztere alle linksberechenbaren reellen Zahlen beschleunigbar sind.

Für den Begriff der Beschleunigbarkeit, der unter Verwendung von linksberechenbaren Approximationen für linksberechenbare reelle Zahlen definiert ist, wird Folgendes gezeigt. Der Begriff ist robust, insofern als eine reelle Zahl, die $\rho$-beschleunigbar für ein $\rho<1$ ist, tatsächlich $\rho$-beschleunigbar für alle $\rho>0$ bezüglich beliebiger linksberechenbarer Approximationen der reellen Zahl ist. Außerdem ist die Beschleunigbarkeit eine Gradeigenschaft, das heißt, in einem Solovay-Grad ist entweder jede oder keine reelle Zahl beschleunigbar. Darüber hinaus sind Martin-Löf-zufällige linksberechenbare reelle Zahlen niemals beschleunigbar, während alle linksberechenbaren reellen Zahlen beschleunigbar sind, die nicht hoch im Sinne der Berechenbarkeitstheorie sind. Einige dieser Ergebnisse lassen sich für die monotone Solovay-Reduzierbarkeit auf alle reellen Zahlen erweitern, insbesondere die Robustheit in Bezug auf die Wahl eines Werts~$\rho>0$ und die Unbeschleunigbarkeit von Martin-Löf-zufälligen reellen Zahlen. Martin-Löf-zufällig zu sein ist weder für alle noch nur für die linksberechenbaren reellen Zahlen äquivalent zur Unbeschleunigbarkeit. Das erste Ergebnis wird im Folgenden durch die Konstruktion eines rechtsberechenbaren Gegenbeispiels gezeigt, das heißt, durch eine rechtsberechenbare reelle Zahl, die weder Martin-Löf-zufällig noch be\-schleunig\-bar ist. Das zweite, interessantere und schwierigere, Ergebnis ist von Hölzl und Janicki~\cite{Hoelzl-Janicki-2023}, die ein linksberechenbares Gegenbeispiel konstruierten.

Drittens kann der Satz von Barmpalias und Lewis-Pye unter Verwendung der monotonen Solovay-Reduzierbarkeit äquivalent umformul\-iert werden, so dass sich die Umformulierung auf alle reellen Zahlen erweitern lässt. Diese Erweiterung ist eines der Hauptergebnisse dieser Arbeit. Eine entsprechende Umformulierung mittels Solovay-Reduzierbarkeit ist im Allgemeinen falsch und gilt tatsächlich für keine linksberechenbare reelle Zahl.