💻 computer science

A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem

Dieser Artikel präsentiert einen konstruktiven Beweis für den Satz von Rice und das Halteproblem, der ohne das Gesetz vom ausgeschlossenen Dritten oder Diagonalisierung auskommt und stattdessen auf einer Zwei-Zeugen-Konstruktion basiert, die die Unentscheidbarkeit des zehnten Hilbertschen Problems nutzt.

Ursprüngliche Autoren: Jonathan Brossard

Veröffentlicht 2026-04-21

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jonathan Brossard

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 vor, Sie haben einen riesigen, magischen Koffer mit unzähligen Computerprogrammen. Die Frage, die sich Informatiker seit Jahrzehnten stellen, lautet: Können wir ein universelles Werkzeug bauen, das uns sofort sagt, was jedes dieser Programme tut?

Genau hier kommt der Satz von Rice ins Spiel. Er sagt: „Nein, das geht nicht." Es gibt keine allgemeine Regel, um zu prüfen, ob ein Programm eine bestimmte Eigenschaft hat (z. B. „endet es jemals?" oder „berechnet es eine Primzahl?"), es sei denn, die Eigenschaft ist völlig trivial (wie „ist es ein Programm?").

Bisherige Beweise dafür waren wie ein Zauberkunststück mit einem Trick: Sie nutzten logische „Ausnahmen" (das Gesetz des ausgeschlossenen Dritten), die in der strengen Welt der konstruktiven Mathematik verboten sind. Man könnte sagen, sie sagten: „Entweder endet das Programm oder es endet nicht – und wir nutzen diesen Widerspruch, um zu beweisen, dass wir es nicht vorhersagen können."

Jonathan Brossard hat in diesem Papier nun einen neuen, reinen Weg gefunden. Er hat den Trick entfernt und den Beweis so gebaut, dass er auch in einer Welt funktioniert, in der man nur das beweisen darf, was man tatsächlich konstruieren kann.

Hier ist die einfache Erklärung seiner Methode mit ein paar kreativen Analogien:

1. Das alte Problem: Der „Todesfall" (Das immer endlose Programm)

Stellen Sie sich vor, Sie wollen beweisen, dass man nicht vorhersagen kann, ob ein Programm aufhört zu laufen.

Der alte Weg: Man baut ein Programm, das sich selbst betrachtet. Wenn der Prüfer sagt „Es hört auf", macht das Programm genau das Gegenteil (es läuft ewig). Wenn der Prüfer sagt „Es läuft ewig", stoppt es. Das ist ein logischer Widerspruch. Aber um das zu tun, muss man annehmen: „Entweder es läuft oder es läuft nicht." Das ist der verbotene logische Schritt.
Das neue Problem: Man musste auch prüfen, wie sich ein Programm verhält, das niemals endet (ein Programm, das in einer Endlosschleife feststeckt). Man musste sich fragen: „Gehört dieses ewige Nichtstun zu unserer Eigenschaft?" Die Antwort darauf war oft der Knackpunkt, der den Beweis „klassisch" machte.

2. Die neue Lösung: Der „Zwillings-Test" (Die zwei Zeugen)

Brossard nutzt eine clevere Taktik, die wir den „Zwillings-Test" nennen könnten. Er braucht keine Selbstbetrachtung und keine Annahmen über das ewige Nichtstun.

Stellen Sie sich vor, Sie haben ein Rätsel: Kann eine bestimmte mathematische Gleichung (ein Diophantisches Polynom) gelöst werden?

Es gibt eine Gleichung, die vielleicht eine Lösung hat, vielleicht aber auch nicht.
Brossard baut nun für jede dieser Gleichungen zwei fast identische Programme, nennen wir sie Bruder A und Bruder B.

Wie funktionieren diese Brüder?

Wenn die Gleichung eine Lösung hat:
- Bruder A verwandelt sich sofort in ein Programm, das niemals endet (wie ein Hamster im Rad).
- Bruder B verwandelt sich sofort in ein Programm, das sofort fertig wird (wie ein Sprinter, der das Ziel erreicht).
- Ergebnis: Ein Prüfer würde sofort merken: „A ist anders als B!"
Wenn die Gleichung KEINE Lösung hat:
- Beide Brüder suchen vergeblich nach einer Lösung. Da sie nie eine finden, tun sie exakt dasselbe: Sie laufen beide ewig weiter und werden nie fertig.
- Ergebnis: Ein Prüfer kann keinen Unterschied zwischen A und B erkennen. Sie sind wie zwei Zwillinge, die sich nicht unterscheiden lassen.

3. Der große Trick: Der Unterschied als Messinstrument

Jetzt kommt der geniale Teil. Brossard sagt: „Angenommen, es gäbe ein magisches Werkzeug, das jede Eigenschaft von Programmen prüfen kann."

Dieses Werkzeug würde Bruder A und Bruder B untersuchen.
Wenn die Gleichung lösbar ist, würde das Werkzeug sagen: „A ist nicht haltbar, B ist haltbar." Der Unterschied ist 1.
Wenn die Gleichung unlösbar ist, würde das Werkzeug sagen: „A und B sind identisch." Der Unterschied ist 0.

Das Problem:
Wenn wir dieses magische Werkzeug hätten, könnten wir damit jede mathematische Gleichung lösen! Wir würden einfach die Brüder bauen, das Werkzeug fragen, und schon wüssten wir, ob die Gleichung eine Lösung hat.

Aber wir wissen aus einem anderen, sehr soliden mathematischen Satz (dem MRDP-Theorem, auch bekannt als Hilberts zehntes Problem), dass es unmöglich ist, ein solches Werkzeug zu bauen, das alle Gleichungen löst.

Der Schluss:
Da das Ergebnis (die Lösung der Gleichung) unmöglich zu berechnen ist, muss auch das Werkzeug, das die Programme prüft, unmöglich existieren.

Warum ist das so wichtig?

Keine Magie: Der Beweis braucht keine „Entweder-Oder"-Annahmen. Er baut einfach zwei Programme und schaut auf ihren Unterschied.
Kein Selbstbezug: Die Programme schauen sich nicht selbst an. Sie schauen nur auf eine mathematische Gleichung.
Konstruktiv: Man kann die Programme tatsächlich programmieren. Es ist kein theoretisches „Es gibt sie nicht", sondern ein „Wenn sie existierten, könnten wir das Unmögliche tun".

Zusammenfassung in einem Satz

Statt zu sagen: „Wenn du versuchst, das Unmögliche zu lösen, wirst du in einen logischen Widerspruch geraten," sagt Brossard: „Wenn du ein Werkzeug hättest, das Programme prüft, könntest du damit mathematische Rätsel lösen, die nachweislich unlösbar sind. Da diese Rätsel unlösbar sind, kann das Werkzeug nicht existieren."

Es ist, als würde man beweisen, dass es keinen perfekten Wettervorhersage-Roboter gibt, indem man zeigt: „Wenn es ihn gäbe, könnte er auch vorhersagen, ob ein Würfel, den man in 100 Jahren wirft, eine 6 zeigt – was wir wissen, unmöglich ist."

1. Problemstellung

Das Paper adressiert die Beweise von zwei fundamentalen Ergebnissen der theoretischen Informatik:

Rice's Theorem: Keine nicht-triviale semantische Eigenschaft von Programmen ist entscheidbar.
Das Halteproblem: Es gibt keinen Algorithmus, der für ein beliebiges Programm und eine Eingabe entscheiden kann, ob das Programm hält.

Das zentrale Problem: Klassische Beweise für diese Sätze basieren auf dem Gesetz des ausgeschlossenen Dritten (LEM - Law of Excluded Middle) und verwenden oft Diagonalisierung oder Selbstreferenz.

Bei Rice's Theorem wird typischerweise ein Fallunterscheidung (Case Split) bezüglich der Eigenschaft $P$ für das immer-divergierende Programm $\bot$ ( $P(\bot) \lor \neg P(\bot)$ ) durchgeführt.
Beim Halteproblem wird ein Programm konstruiert, das genau dann hält, wenn der hypothetische Entscheider sagt, es halte nicht (Diagonalisierung).

Diese klassischen Methoden sind in der konstruktiven Logik (intuitionistische Logik) nicht gültig, da sie keine konstruktive Information liefern und in Systemen wie Coq oder Agda nicht direkt extrahiert werden können. Bisherige konstruktive Beweise (z. B. in der coq-library-undecidability) leiten Rice's Theorem oft vom Halteproblem ab, welches selbst bereits durch Diagonalisierung bewiesen wurde.

Ziel des Papers: Einen Beweis zu liefern, der vollständig konstruktiv ist, keine Diagonalisierung verwendet, keine Annahmen über $P(\bot)$ trifft und die Unentscheidbarkeit direkt auf das 10. Hilbert-Problem (MRDP-Theorem) zurückführt.

2. Methodik

Der Beweis folgt einem reduktiven Ansatz, der die Unentscheidbarkeit semantischer Eigenschaften direkt mit der Unentscheidbarkeit diophantischer Gleichungen verknüpft.

A. Das Modell: Schritt-indizierte Semantik

Statt auf Turing-Maschinen oder partielle rekursive Funktionen im klassischen Sinne zurückzugreifen, verwendet das Paper ein schritt-indiziertes Berechnungsmodell.

Programme werden als Funktionen $e: \mathbb{N} \to (\mathbb{N} \to \text{option } \mathbb{N})$ modelliert, wobei der zweite Parameter ein "Fuel" (Schrittlimit) ist.
Observationale Äquivalenz ( $\simeq$ ): Zwei Programme sind äquivalent, wenn sie für jede Eingabe ab einem bestimmten Fuel-Wert $N$ identische Ausgaben liefern. Dies ist eine konstruktive Definition von Extensionalität, die keine Entscheidung über Konvergenz/Divergenz für ein einzelnes $x$ erfordert.

B. Die Zwei-Zeugen-Konstruktion (Two-Witness Construction)

Dies ist der Kern der neuen Methode. Gegeben sei eine nicht-triviale semantische Eigenschaft $P$ mit zwei expliziten Zeugen:

$e_0$ : Ein Programm, für das $\neg P(e_0)$ gilt.
$e_1$ : Ein Programm, für das $P(e_1)$ gilt.

Für jedes diophantische Polynom $D$ (mit ganzzahligen Koeffizienten) werden zwei neue Programme $S^0_D$ und $S^1_D$ konstruiert:

Suche: Beide Programme enumerieren systematisch alle Tupel $\vec{x}$ und prüfen, ob $D(\vec{x}) = 0$ gilt.
Verhalten bei Lösung:
- Wenn eine Lösung gefunden wird (bei Schritt $n$ ), übernimmt $S^1_D$ das Verhalten von $e_1$ (für alle Fuel $\ge n$ ).
- $S^0_D$ übernimmt das Verhalten von $e_0$ .
Verhalten bei keiner Lösung:
- Wenn $D$ keine Lösung hat, divergieren beide Programme $S^0_D$ und $S^1_D$ für immer (verhalten sich wie $\bot$ ).

Der entscheidende Trick:

Wenn $D$ lösbar ist: $P(S^1_D) \iff P(e_1)$ (wahr) und $P(S^0_D) \iff P(e_0)$ (falsch). Ein hypothetischer Entscheider $Decide_P$ würde unterschiedliche Werte liefern.
Wenn $D$ unlösbar ist: $S^0_D \simeq S^1_D \simeq \bot$ . Da $P$ eine semantische Eigenschaft ist (respektiert $\simeq$ ), gilt $P(S^0_D) \iff P(S^1_D)$ . Der Entscheider muss für beide denselben Wert zurückgeben.
Wichtig: Es wird niemals der Wert von $P(\bot)$ bestimmt oder eine Fallunterscheidung darüber getroffen. Die Äquivalenz im unlöslichen Fall folgt rein aus der Extensionalität.

C. Der Widerspruch

Angenommen, es gäbe einen Entscheider $Decide_P$ für $P$ . Man könnte eine Funktion $F(D) = Decide_P(S^1_D) - Decide_P(S^0_D)$ konstruieren.

Ist $D$ lösbar, ist $F(D) = 1 - 0 = 1$ .
Ist $D$ unlösbar, ist $F(D) = x - x = 0$ .
Dies würde eine entscheidbare Funktion für die Lösbarkeit diophantischer Gleichungen liefern, was dem MRDP-Theorem (Unentscheidbarkeit des 10. Hilbert-Problems) widerspricht.

3. Schlüsselbeiträge

Konstruktiver Beweis ohne LEM: Der Beweis ist in intuitionistischer Logik gültig. Er vermeidet das Gesetz des ausgeschlossenen Dritten vollständig, insbesondere die klassische Fallunterscheidung $P(\bot) \lor \neg P(\bot)$ .
Keine Diagonalisierung: Im Gegensatz zu klassischen Beweisen (Rice, Turing) wird kein Programm konstruiert, das sich selbst referenziert oder seinen eigenen Index kennt. Die Konstruktion von $S^b_D$ ist rein explizit und algorithmisch basierend auf dem Polynom $D$ .
Direkte Reduktion auf MRDP: Statt über das Halteproblem zu gehen, wird Rice's Theorem direkt auf die Unentscheidbarkeit des 10. Hilbert-Problems reduziert. Das Halteproblem wird dann als einfaches Korollar (Instantiierung von $P$ als "Terminates") abgeleitet.
Formalisierung in Rocq (Coq): Der gesamte Beweis wurde im Proof Assistant Rocq (eine Variante von Coq) formalisiert.
- Der Code ist vollständig konstruktiv.
- Die einzige externe Axiomatik ist die Unentscheidbarkeit des 10. Hilbert-Problems (importiert aus coq-library-undecidability), die selbst konstruktiv bewiesen wurde.
- Alle Theoreme (Rice, Halting) sind "Closed under the global context" (keine zusätzlichen klassischen Axiome).
Vermeidung von Totalitätsbedingungen: Durch das Design, dass die Zeugenprogramme $e_0, e_1$ ihr gesamtes "Fuel-Budget" unverändert erhalten, wenn eine Lösung gefunden wird, entfällt die Notwendigkeit, dass die Zeugen total (immer haltend) sein müssen. Der Beweis gilt für beliebige partielle Programme.

4. Ergebnisse

Rice's Theorem (Konstruktiv): Es wurde bewiesen, dass für jede nicht-triviale semantische Eigenschaft $P$ kein Programm existiert, das $P$ entscheidet, unter der alleinigen Annahme der Unentscheidbarkeit des 10. Hilbert-Problems.
Halteproblem (Konstruktiv): Die Unentscheidbarkeit des Halteproblems folgt unmittelbar aus Rice's Theorem, indem $P$ als Eigenschaft "Terminiert auf Input 0" definiert wird.
Axiom-Abhängigkeit: Das Paper zeigt, dass die Unentscheidbarkeit dieser Probleme in der konstruktiven Mathematik äquivalent zur Unentscheidbarkeit diophantischer Gleichungen ist. Es werden keine klassischen Prinzipien wie LEM oder Double-Negation-Elimination benötigt.
Grad-Hierarchie: Es wird diskutiert, dass die Unentscheidbarkeit bereits durch Polynome vom Grad 4 (nach dem MRDP-Theorem) gesättigt ist ( $Rice(4) = Rice(\infty)$ ). Ob Grad 3 oder 2 ausreichen, bleibt eine offene Frage.

5. Bedeutung und Implikationen

Theoretische Informatik: Das Paper schließt eine Lücke in der konstruktiven Berechenbarkeitstheorie. Es zeigt, dass die Unentscheidbarkeit fundamentaler Probleme nicht zwingend auf "seltsamen" selbstreferenziellen Paradoxien beruht, sondern auf der inhärenten Komplexität der diophantischen Arithmetik.
Verifikation und Program Extraction: Da der Beweis konstruktiv ist, kann er in Systemen wie Coq oder Agda verwendet werden, um Unentscheidbarkeitsargumente zu internalisieren, ohne auf klassische Axiome zurückzugreifen. Dies ermöglicht die Extraktion von verifizierten Programmen, die auf diesen Beweisen basieren.
Reverse Mathematics: Es trägt zur "Constructive Reverse Mathematics" bei, indem es präzise identifiziert, welche nicht-konstruktiven Prinzipien für Rice's Theorem tatsächlich notwendig sind (nämlich keine, solange MRDP als gegeben angenommen wird).
Praktische Relevanz: Die Konstruktion der Zeugenprogramme $S^b_D$ ist explizit und implementierbar. Das Paper liefert sogar ein C-Programm (undecidable.c), das diese Konstruktion demonstriert und zeigt, wie die Terminierung eines solchen Programms an ein offenes Problem der Zahlentheorie (Summe von drei Kubikzahlen) gekoppelt ist.

Zusammenfassend bietet das Paper einen eleganten, "diagonalisierungsfreien" Weg, um die Grenzen der Berechenbarkeit zu verstehen, und stellt sicher, dass diese Grenzen auch in rein konstruktiven Logiksystemen bestehen bleiben.