collatz/12-unentscheidbarkeit.md

12 · Der Horizont: Unentscheidbarkeit

Stell dir ein weites Feld vor. Um das Feld läuft ein Zaun, und in den Zaun sind Tore eingelassen — hinter jedem steht eine Frage, die die Mathematik bis heute nicht beantwortet hat. Eines dieser Tore hast du durch dieses ganze Buch begleitet: Dahinter steht die Frage, ob jede Startzahl am Ende bei 1 landet. Es ist verschlossen. Seit fast einem Jahrhundert rüttelt man daran, und es ist nicht aufgegangen.

Die Frage ist nicht, wie man das Tor aufkriegt. Die Frage ist, was für ein Schloss daran hängt. Denn es gibt zwei grundsätzlich verschiedene Gründe, warum ein Tor zu bleiben kann. Erstens: Es fehlt der Schlüssel — er existiert vielleicht, aber niemand hat ihn bisher geschmiedet. Zweitens: Das Schloss ist so gebaut, dass kein Schlüssel dieser Welt es je öffnen kann. Dass Tore der zweiten Art wirklich existieren, ist keine Vermutung, sondern einer der erstaunlichsten Sätze der Mathematik.

{width=90%}

Gödel 1931: wahre Sätze ohne Beweis

Zwei Begriffe vorweg. Ein formales System ist ein Regelwerk: Axiome — Grundaussagen, die ohne Beweis gesetzt werden — plus Regeln, nach denen weitere Aussagen folgen. Beweisbar heißt ein Satz darin, wenn er sich so herleiten lässt; widerlegbar, wenn sich sein Gegenteil herleiten lässt. Widerspruchsfrei heißt das System, wenn nie beides zugleich folgt.

Dazu der Satz von 1931: In jedem widerspruchsfreien, hinreichend starken formalen System — stark genug für die gewöhnliche Arithmetik — gibt es wahre Sätze, die sich darin weder beweisen noch widerlegen lassen (Gödel 1931). Wahr heißt hier: für die natürlichen Zahlen richtig, so wie man sie kennt. Solche Sätze heißen unentscheidbar im System; die Axiome reichen nicht hin, sie zu fassen. Gödel zeigte außerdem: Ein solches System kann seine eigene Widerspruchsfreiheit nicht aus sich heraus begründen.

Dann die Bremsung, denn hier beginnt die Redlichkeit. Gödels Satz sagt, dass es solche Sätze gibt. Er sagt nicht, welches berühmte offene Problem nun heimlich einer von ihnen ist. Er ist eine Aussage über Systeme — keine Diagnose für ein einzelnes ungelöstes Problem. Wer daraus schließt, die Collatz-Vermutung sei mit Sicherheit ein solcher Fall, behauptet etwas, das niemand bewiesen hat.

Die Kontinuumshypothese: ein bewiesener Status

Dass sich der Status eines einzelnen Problems dennoch beweisen lässt, zeigt das prominenteste Beispiel der Logik. Die Mathematik kennt Unendlichkeit in Stufen. Die natürlichen Zahlen lassen sich der Reihe nach aufzählen; die reellen Zahlen, alle Punkte auf der Zahlenlinie, übersteigen jede solche Aufzählung — ihre Unendlichkeit ist streng größer. Die Kontinuumshypothese fragt, ob es dazwischen noch etwas gibt: eine Stufe, größer als die der natürlichen und kleiner als die der reellen Zahlen.

Entscheiden lässt sich so etwas nur relativ zu einem Axiomensystem. Das Standard-System der Mathematik heißt ZFC — die Axiome der Mengenlehre, in deren Sprache sich die heutige Mathematik ganz aufschreiben lässt. Kurt Gödel zeigte 1940: Die Kontinuumshypothese lässt sich aus ZFC nicht widerlegen. Paul Cohen zeigte 1963: Sie lässt sich aus ZFC nicht beweisen. Zusammengelesen — unter der Annahme, dass ZFC widerspruchsfrei ist — heißt das: Die Kontinuumshypothese ist unabhängig von ZFC.

Was dieses Ergebnis leistet: Es beweist, was aus diesen Axiomen niemals bewiesen und niemals widerlegt werden kann. Nicht „wir finden den Beweis einfach nicht“ — die Axiome entscheiden die Frage schlicht nicht. Das ist ein bewiesener Status.

Die Collatz-Vermutung hat keinen solchen Status. Sie ist offen, und es ist nichts bekannt, das ihre Unbeweisbarkeit oder ihre Unabhängigkeit begründen würde. Kein Gödel-Argument, kein Cohen-Werkzeug, kein Teilergebnis dieser Art existiert für die klassische Regel.

Conway 1972: die Familie ist unentscheidbar

Hier zählt, was Conways Satz von 1972 für die Vermutung bedeutet — und was nicht.

Bewiesen ist etwas, das Collatz berührt — aber auf eine Weise, die man ganz genau auseinandernehmen muss. Verallgemeinerte Collatz-Regeln entstehen so: Man wählt eine Zahl d, sortiert die ganzen Zahlen nach ihrem Rest bei Division durch d und legt für jede Restklasse eine eigene lineare Vorschrift fest — aus n wird a·n + b, mit festen Zahlen a und b. Das Prinzip kennst du vom 5n+1-Problem; Conways Familie umfasst unzählige solcher Regeln auf einmal. Die klassische Regel ist der Spezialfall d = 2 — zwei Restklassen: gerade und ungerade.

John Conway bewies 1972: Diese Familie ist rechneruniversell. Verallgemeinerte Collatz-Regeln können jeden beliebigen Rechenvorgang simulieren; jedes Programm lässt sich als eine solche Regel verkleiden. Die Folge ist hart: Es gibt kein Schritt-für-Schritt-Verfahren, das zu jeder Regel der Familie entscheidet, ob jede Bahn bei 1 landet (Conway 1972). So eine Frage heißt algorithmisch unentscheidbar — nicht „schwer“, sondern für kein Verfahren lösbar. Ein solches Allverfahren würde nämlich das Anhalte-Problem der Informatik lösen: die Frage, ob ein beliebiges Programm irgendwann stoppt. Und genau die ist nachweislich unlösbar.

Conway goss den Mechanismus 1987 in die Mini-Programmiersprache FRACTRAN. Ein FRACTRAN-Programm ist nichts als eine geordnete Liste von Brüchen. Der Startwert ist eine Zahl; jeder Schritt multipliziert sie mit dem ersten Bruch der Liste, der ein ganzzahliges Ergebnis liefert; passt kein Bruch mehr, endet das Programm. Jeder Lauf ist eine Collatz-artige Iteration: Fallunterscheidung per Teilbarkeit, dann eine einfache arithmetische Aktualisierung. Conways Demonstrationsprogramm PRIMEGAME kommt mit 14 Brüchen aus, und die Zweierpotenzen, die dabei auftauchen, tragen genau die Primzahlen als Exponenten.

Kurtz und Simon verschärften das Bild 2007. Sie untersuchten eine natürliche Verallgemeinerung, die der klassischen Regel sehr nahe kommt, und bewiesen: Schon zu entscheiden, ob bei so einer Regel alle Bahnen konvergieren, ist so schwer wie die allgemeine Frage, ob ein Programm für jede mögliche Eingabe irgendwann endet (Kurtz und Simon 2007). Auch das ist algorithmisch unentscheidbar.

Der feine Unterschied: Familie, nicht Einzelregel

Diese Ergebnisse gelten für Familien von Regeln. Sie zeigen nicht, dass die einzelne Regel 3n+1 unentscheidbar ist, und sie lösen die Vermutung nicht.

Was sie zerstören, ist die Hoffnung auf eine einheitliche Technik, die alle diese Regeln auf einmal behandelt — so eine Technik kann für die Familie nicht existieren, das ist bewiesen. Deshalb scheitern entsprechende Beweisversuche so verlässlich. Die klassische Regel bleibt die offene Ausnahme.

Im Bild: Die Ergebnisse betreffen den ganzen Zaun voller Tore. Dem einen Tor mit der 3n+1-Frage haben sie nichts getan. Es steht, wie es stand.

Könnte Collatz ein Gödel-Tor sein?

Damit zur Frage, die dieses Kapitel angekündigt hat. Die Antwort hat drei Stufen.

Erstens: denkbar. Niemand hat ausgeschlossen, dass die klassische Vermutung in der üblichen Arithmetik unbeweisbar ist. Diese Möglichkeit ist logisch offen.

Zweitens: unbekannt. Kein Beweis, kein Teilergebnis, kein Hinweis zeigt in diese Richtung. „Offen“ heißt hier genau das: Wir wissen es nicht — weder, dass sich die Vermutung beweisen lässt, noch, dass sie sich nicht beweisen lässt.

Drittens: der Unterschied. Die beiden Tor-Typen darf man nicht verwechseln. Bei der Kontinuumshypothese wurde das Schloss vermessen: Gödel und Cohen bewiesen den Status. Bei Collatz steht nur fest, dass das Tor zu ist.

Und das Gedankenspiel, ganz vorsichtig: Wäre die klassische Vermutung in der üblichen Arithmetik unentscheidbar, wäre das selbst eine Sensation — ein großes neues Resultat der Logik, in der Tradition von Gödel 1931 und Cohen 1963. Es hätte feine logische Konsequenzen bis in die Grundlagen hinein. Mehr davon auszumalen, wäre Spekulation: Diesen Beweis gibt es nicht. Aber die Kontinuumshypothese zeigt, was so ein Status wäre: keine Antwort „wahr oder falsch“, sondern die Auskunft, dass die Axiome die Frage nie werden entscheiden können.

Theorem (Gödel 1931): In jedem widerspruchsfreien, hinreichend starken formalen System gibt es wahre Sätze, die sich darin weder beweisen noch widerlegen lassen. Eine Aussage über Systeme — keine Diagnose für einzelne offene Probleme.

Theorem (Gödel 1940; Cohen 1963): Die Kontinuumshypothese ist unabhängig von ZFC — bewiesen unter der Annahme, dass ZFC widerspruchsfrei ist. Ein präziser Status.

Theorem (Conway 1972; Kurtz und Simon 2007): Für Familien verallgemeinerter Collatz-Regeln gibt es kein Allverfahren, das entscheidet, ob jede Bahn bei 1 landet. Die Familien sind unentscheidbar — die klassische Regel ist von diesen Ergebnissen nicht getroffen.

Offen (Stand 2026): Die klassische Vermutung. Weder bewiesen noch widerlegt, weder als unentscheidbar noch als unabhängig nachgewiesen; nichts ist bekannt, das in diese Richtung weist.

Bleibt das Bild. Es gibt zwei Arten verschlossener Tore: solche, deren Schloss von vornherein keinen Schlüssel dieser Welt passieren lässt — bewiesen, von Gödel und Cohen vermessen — und solche, denen schlicht der Schlüssel fehlt. Nicht jedes verschlossene Tor ist ein Gödel-Tor. Manche sind nur noch nicht geschmiedet. Zu welcher Art das Tor mit der 3n+1-Frage gehört, weiß niemand; redlich endet der Ausblick hier nur mit: Es könnte beides sein. Das ist der Horizont dieses Buchs — kein Versprechen, sondern die Stelle, an der das Wissen aufhört und die Neugier weitergeht.