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

Eine reelle Zahl ist linksberechenbar, wenn sie eine linksberechenbare Approximation besitzt, dass heißt, es gibt eine berechenbare nichtfallende Folge a0, a1, . . . von rationalen Zahlen, die gegen die reelle Zahl konvergiert. Weiter ist eine reelle Zahl α auf eine reelle Zahl β Solovay-reduzierbar, wenn es eine partiell berechenbare Funktion g gibt, die jede rationale Zahl q < β auf eine rationale Zahl g(q) < α abbildet, so dass für eine reelle Konstante c und alle q < β gilt α − g(q) < c(β − q).

Mittels der Solovay-Reduzierbarkeit kann die Geschwindigkeit verglichen werden, mit der linksberechenbare Zahlen approximiert werden können. Falls eine reelle Zahl α Solovay-reduzierbar auf eine linksberechenbare reelle Zahl β ist, dann ist α ebenfalls linksberechenbar und gibt es für jede linksberechenbare Approximation von β eine linksberechenbare Approximation von α, 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 Charakterisierungen erlauben. Zum Beispiel sind nach Ergebnissen von Solovay und von Calude, Hertling, Khoussainov und Wang die Martin-Löf-zufälligen linksberechenbaren reellen Zahlen genau die Haltewahrscheinlichkeiten universeller Turingmaschinen. Kŭcera und Slaman 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 β ist genau dann Martin-Löf-zufällig, wenn jede linksberechenbare reelle Zahl α auf β reduzierbar ist, und dass letztere Aussage sogar bezüglich beliebiger linksberechenbarer Approximationen von α und β gilt.

Folglich sind beliebige Martin-Löf-zufällige linksberechenbare reelle Zahlen α und β bezüglich beliebiger linksberechenbarer Approximationen a0, a1, . . . und b0, b1, . . . von α beziehungsweise β gegenseitig Solovay-reduzierbar, das heißt, es gibt reelle Zahlen c > 0 und d, so dass füur alle n gilt c < (α − an) / (β − bn) < d. (2)

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 konvergieren die Werte sogar: der Grenzwert lim n→∞ (α − an) / (β − bn) existiert und hängt nicht von der Wahl der Linksapproximationen von α und β ab.

Eine linksberechenbare reelle Zahl α ist ρ-beschleunigbar, falls sie eine Linksapproximation a0, a1, . . . besitzt, so dass für eine berechenbare Funktion f gilt lim inf n→∞ (α − af (n)) / (α − an) ≤ ρ, und sie ist beschleunigbar, falls sie ρ-beschleunigbar für ein ρ < 1 ist. Merkle and Titov 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. 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-Reduzierbarkeit, außer dass zusätzlich verlangt wird, dass die Funktion g in (2) monoton steigend ist, das heißt, es gilt g(q) ≤ 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-Reduzierbarkeit 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 ∆02, 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äare, 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 ρ-beschleunigbar für ein ρ < 1 ist, tatsächlich ρ-beschleunigbar für alle ρ > 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 ρ > 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 beschleunigbar ist. Das zweite, interessantere und schwierigere, Ergebnis ist von Hölzl und Janicki, die ein linksberechenbares Gegenbeispiel konstruierten.

Drittens kann der Satz von Barmpalias und Lewis-Pye unter Verwendung der monotonen Solovay-Reduzierbarkeit äquivalent umformuliert 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äachlich für keine linksberechenbare reelle Zahl.