🔢 mathematics

Inexpressibility in Exp-Minus-Log

Dieses Papier stellt fest, dass das Exp-Minus-Log-System, das elementare Funktionen auf eine Konstante und eine einzige zweistellige Operation reduziert, nur berechenbare Zahlen ausdrücken kann, wodurch bewiesen wird, dass Chaitins $\Omega_U$ innerhalb dieses Rahmens nicht ausdrückbar ist.

Ursprüngliche Autoren: Mark Carney

Veröffentlicht 2026-05-05

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mark Carney

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine magische, allmächtige Küche vor. In dieser Küche verfügen Sie nicht über ein vollständiges Werkzeugset wie Mixer, Öfen und Rührgeräte. Stattdessen besitzen Sie nur ein einziges Spezialwerkzeug, nennen wir es „Magischer Zauberstab" (in der Arbeit als E dargestellt), und eine einzige Zutat: die Zahl 1.

Die Arbeit von Mark Carney untersucht, was passiert, wenn Sie versuchen, jede mögliche Zahl unter Verwendung ausschließlich dieses einen Zauberstabs und dieser einen Zutat zu „kochen".

Das Rezept des Magischen Zauberstabs

Der Zauberstab funktioniert auf sehr spezifische Weise. Wenn Sie ihn auf zwei Dinge richten, sagen wir A und B, führt er einen speziellen Trick aus: Er nimmt die Exponentialfunktion von A (eine ausgefallene Art, sie sehr schnell wachsen zu lassen) und subtrahiert den Logarithmus von B (eine Art, sie zu verkleinern).

Die Formel: Ergebnis = exp(A) - log(B)

Die ursprünglichen Forscher (Odrzywo lek) zeigten, dass Sie mit nur diesem einen Trick und der Zahl 1 tatsächlich fast alles nachbilden können, was wir gewöhnlich als „Standardmathematik" bezeichnen. Sie können ganze Zahlen, Brüche, die Zahl $\pi$ , $e$ und sogar komplexe Funktionen wie Sinus und Kosinus konstruieren. Es ist, als könnte man eine ganze Hochzeitstorte backen, indem man nur einen einzigen Löffel und eine Tasse Mehl verwendet.

Die große Frage: Können Sie alles kochen?

Die Arbeit stellt eine tiefere Frage: Gibt es etwas, das diese Küche nicht herstellen kann?

Um dies zu beantworten, vergleicht der Autor diese „Magische-Zauberstab"-Küche mit einer bekannten Menge von Zahlen, den EL-Zahlen (benannt nach dem Mathematiker Timothy Chow). Die Arbeit beweist, dass die Magische-Zauberstab-Küche und Chows Küche tatsächlich derselbe Ort sind. Sie können genau dieselbe Liste von Zahlen herstellen.

Die „unkochbare" Zutat: Chaitins $\Omega$

Der Autor führt dann eine sehr seltsame, theoretische Zutat ein, die Chaitins $\Omega$ (Omega) genannt wird.

Was ist das? Stellen Sie sich eine Zahl vor, die die Wahrscheinlichkeit darstellt, dass ein Computerprogramm stoppt (terminiert) oder für immer weiterläuft.
Warum ist es besonders? Diese Zahl ist „nicht berechenbar". Es ist nicht nur eine Zahl, die wir noch nicht berechnet haben; es ist mathematisch unmöglich für jeden Computer (egal wie leistungsfähig), jemals ihre exakten Ziffern aufzuschreiben oder ihre nächste Ziffer vorherzusagen. Es ist eine Zahl, die existiert, aber sie ist grundsätzlich für jeden schrittweisen Rezeptweg „unerreichbar".

Die Hauptentdeckung

Die Arbeit beweist eine einfache, aber mächtige Regel: Jede Zahl, die Sie mit dem Magischen Zauberstab herstellen können, ist „berechenbar".

Hier ist die Logik in einfacher Sprache:

Die Zutaten sind sicher: Sie beginnen mit der Zahl 1 (die leicht zu berechnen ist).
Der Prozess ist sicher: Der Magische Zauberstab führt nur zwei Dinge aus: exp und log. Die Arbeit zeigt, dass diese Werkzeuge, wenn Sie ihnen eine Zahl zuführen, die ein Computer berechnen kann, ein Ergebnis liefern, das ein Computer ebenfalls berechnen kann.
Die Schlussfolgerung: Da Sie mit einer berechenbaren Zahl beginnen und nur berechenbare Werkzeuge verwenden, muss jede einzelne Zahl, die Sie in diesem System konstruieren können, berechenbar sein.

Da Chaitins $\Omega$ nicht berechenbar ist, ist es unmöglich, sie in dieser Küche zu konstruieren.

Das endgültige Urteil

Die Arbeit schließt mit einem „Formalen Unausdrückbarkeits-Theorem". Einfach ausgedrückt:

Die Magische-Zauberstab-Küche kann eine riesige, unendliche Liste von Zahlen herstellen (einschließlich $\pi$ , $e$ und aller Zahlen, die in Technik und Physik verwendet werden).
Allerdings gibt es einen weiten Ozean von Zahlen, den die Küche niemals berühren kann.
Chaitins $\Omega$ ist das „Aushängeschild" für diese unerreichbaren Zahlen. Es ist ein konkreter Beweis dafür, dass es mathematische Wahrheiten gibt, die sich nicht mit diesem spezifischen Regelsystem ausdrücken lassen.

Eine einfache Analogie

Stellen Sie sich das System des Magischen Zauberstabs als ein Lego-Set vor, das nur rote Steine enthält.

Sie können ein Haus, ein Auto, eine Burg oder ein Raumschiff bauen (diese sind die „berechenbaren" Zahlen wie $\pi$ und $e$ ).
Aber wenn jemand Sie bittet, einen blauen Stein zu bauen, können Sie das nicht. Egal wie viele rote Steine Sie stapeln, Sie werden niemals einen blauen Stein erschaffen.
Chaitins $\Omega$ ist dieser „blaue Stein". Er existiert im Universum der Mathematik, besteht aber aus einem Material (Nicht-Berechenbarkeit), das sich einfach nicht mit den Ihnen zur Verfügung stehenden roten Steinen (dem EML-System) konstruieren lässt.

Zusammenfassend: Die Arbeit bestätigt, dass dieses Ein-Funktions-System zwar unglaublich mächtig ist und fast alle Zahlen abdeckt, die wir im täglichen Leben und in der Wissenschaft verwenden, es jedoch eine harte Grenze gibt. Es kann die „nicht berechenbaren" Zahlen nicht erreichen und beweist, dass einige mathematische Konzepte für diese spezifische Art, sie aufzuschreiben, für immer unerreichbar bleiben.

Technische Zusammenfassung: Unerkennbarkeit in Exp-Minus-Log

Problemstellung
Der Beitrag schließt eine Lücke im theoretischen Verständnis des Exp-Minus-Log-Systems (EML), das ursprünglich von Odrzywo lek [4] definiert wurde. Dieses System reduziert alle elementaren Funktionen, Konstanten und Operationen über komplexen Zahlen auf einen einzigen binären Operator $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$ sowie die Konstante „1". Während Odrzywo leks Arbeit weitgehend konstruktiv und existenziell war – indem sie zeigte, wie sich Standard-Elementarfunktionen ausdrücken lassen –, wurde kein formaler Unausdrückbarkeitsbeweis etabliert. Insbesondere blieb die Frage offen, ob das EML-System nicht-berechenbare reelle Zahlen ausdrücken kann. Dieser Beitrag zielt darauf ab, die Grenzen der EML-Ausdrückbarkeit zu charakterisieren, indem der Berechenbarkeitsstatus aller innerhalb des Systems darstellbaren Zahlen bestimmt wird.

Methodik
Die Autoren wenden eine Kombination aus formaler Logik, berechenbarer Analysis und algorithmischer Informationstheorie an, um die Grenzen von EML zu definieren. Die Methodik verläuft in drei logischen Stufen:

Formale Äquivalenz: Der Beitrag stellt zunächst eine rigorose Äquivalenz zwischen Odrzywo leks EML-Zahlen und Chows EL-Zahlen [2] her. Durch die Bereitstellung expliziter syntaktischer Substitutionen zeigen die Autoren, dass der Körper der EML-Zahlen identisch mit dem Körper der EL-Zahlen ist (dem kleinsten Teilkörper von $\mathbb{C}$ , der unter $\exp$ und $\log$ abgeschlossen ist).
Berechenbarkeitsanalyse: Unter Ausnutzung von Ergebnissen der berechenbaren Analysis (insbesondere [7] und [6]) analysieren die Autoren die Berechenbarkeit der beteiligten Operationen. Sie nutzen die Tatsache aus, dass die Exponentialfunktion auf allen berechenbaren komplexen Eingaben berechenbar ist. Für den Logarithmus behandeln sie die Probleme der Verzweigungsschnitte, indem sie beweisen, dass für jeden definierten EML-Ausdruck das Argument des Logarithmus entweder auf der negativen reellen Achse liegt (wo der Wert über den Betrag und $\pi$ berechenbar ist) oder durch einen rationalen Abstand vom Verzweigungsschnitt getrennt ist.
Induktiver Beweis der Berechenbarkeit: Mittels struktureller Induktion über die Syntax von EML-Ausdrücken beweisen die Autoren, dass jeder definierte EML-Ausdruck eine berechenbare komplexe Zahl ergibt.
Auswahl eines Zeugen: Um die Unerkennbarkeit zu demonstrieren, verwendet der Beitrag Chaitins $\Omega_U$ (die Halte-Wahrscheinlichkeit einer universellen präfixfreien Turingmaschine) als kanonischen Zeugen. Es ist bekannt, dass $\Omega_U$ links-berechenbar aufzählbar, aber nicht berechenbar ist.

Hauptbeiträge und Ergebnisse
Der Beitrag liefert folgende primäre Ergebnisse:

Äquivalenz-Theorem: Die Menge der EML-ausdrückbaren Zahlen wird als genau die Menge von Chows EL-Zahlen bewiesen ($EML = EL$).
Berechenbarkeits-Theorem: Der Beitrag beweist, dass jede EML-ausdrückbare Zahl berechenbar ist. Konkret gilt für jeden geschlossenen EML-Ausdruck $\phi$ , bei dem der Wert definiert ist, dass $[[\phi]]$ eine berechenbare komplexe Zahl ist. Folglich ist die Menge der EML-konstruierbaren reellen Zahlen ( $EML_{\mathbb{R}}$ ) eine Teilmenge der berechenbaren reellen Zahlen ( $\text{Comp}_{\mathbb{R}}$ ).
Unausdrückbarkeits-Theorem: Durch die Kombination der Berechenbarkeit von EML-Zahlen mit der Nicht-Berechenbarkeit von Chaitins $\Omega_U$ beweist der Beitrag formal, dass $\Omega_U \notin EML_{\mathbb{R}}$ .
Maßtheoretische Implikation: Da die Menge der EML-Zahlen abzählbar ist (aufgrund der Abzählbarkeit der Syntax), besitzt die Menge der nicht-EML-ausdrückbaren reellen Zahlen das volle Lebesgue-Maß auf $\mathbb{R}$ . Dies umfasst nicht nur $\Omega_U$ , sondern auch andere Klassen nicht-berechenbarer Zahlen, wie die Binärentwicklung der Haltemenge, Grenzwerte von Specker-Folgen und Martin-Löf-zufällige reelle Zahlen.

Bedeutung und Behauptungen
Der Beitrag behauptet, eine spezifische theoretische Lücke zu schließen, die durch Odrzywo leks ursprüngliche Arbeit hinterlassen wurde, indem er einen formalen Unausdrückbarkeitsbeweis für das EML-System liefert. Die Bedeutung liegt darin, das EML-System nicht nur als Werkzeug zur Generierung von Elementarfunktionen zu charakterisieren, sondern als ein System, das strikt durch Berechenbarkeit begrenzt ist.

Die Autoren rahmen das Ergebnis bescheiden als formale Einschränkung: Während EML ästhetisch ansprechend und nützlich für symbolische Berechnungen und exakte Arithmetik ist (wie in der Einleitung bezüglich CAS-Systemen angemerkt), kann es die „kanonischen" nicht-berechenbaren reellen Zahlen nicht ausdrücken. Der Beitrag schlägt keine neuen Anwendungen oder experimentellen Vorschläge vor; vielmehr dient er als grundlegender Beweis, der feststellt, dass $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ und, spezifischer, $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$ . Das Ergebnis bestätigt, dass die „geschlossenen" Zahlen, die durch diesen einzelnen Operator ausdrückbar sind, strikt auf den Bereich der berechenbaren Zahlen beschränkt sind.