💻 computer science

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

Dit artikel presenteert een constructief bewijs van de stelling van Rice en het haltingprobleem in intuïtionistische logica, zonder gebruik te maken van diagonalisatie of de wet van de uitgesloten derde, door een terugreductie te maken op de onbeslisbaarheid van Hilberts tiende probleem via een tweewitness-construction.

Oorspronkelijke auteurs: Jonathan Brossard

Gepubliceerd 2026-04-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jonathan Brossard

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een superkrachtige computer wilt bouwen die elk mogelijk computerprogramma kan analyseren en direct kan zeggen: "Ja, dit programma stopt ooit" of "Nee, dit programma loopt oneindig door." Of misschien wil je een machine die kan zeggen of een programma een bepaalde eigenschap heeft, zoals "werkt het correct?" of "bevat het een virus?".

De wiskundige Rice's Theorem zegt dat zo'n machine onmogelijk is. Er is geen algoritme dat dit voor elk willekeurig programma kan doen, tenzij het programma heel saai en voorspelbaar is.

Dit artikel van Jonathan Brossard biedt een nieuwe, "constructieve" manier om dit te bewijzen. Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het oude bewijs: De "Zelfmoord-Paradox"

Vroeger bewezen wiskundigen dit door een trucje te gebruiken dat lijkt op een zelfmoord-paradox.

De vergelijking: Stel je voor dat je een spiegel bouwt die een persoon weerspiegelt, maar dan precies het tegenovergestelde doet. Als de persoon glimlacht, maakt de spiegel een boos gezicht. Als de persoon boos is, glimlacht de spiegel.
Het probleem: Wat doet de spiegel als je hem voor een spiegel houdt? Als hij glimlacht, moet hij boos zijn. Als hij boos is, moet hij glimlachen. Dit creëert een logische kringloop (een "diagonalisatie").
Het nadeel: Om dit te bewijzen, moesten de oude wiskundigen een stap zetten die in de "gewone" logica niet altijd mag: ze moesten aannemen dat iets ofwel waar is ofwel onwaar (de "wet van de uitgesloten midden"). Ze moesten ook aannemen dat een programma dat nooit stopt (een "oneindige lus") ofwel wel ofwel niet aan een eigenschap voldoet. Dit is lastig in strikte, bouwkundige logica.

2. De nieuwe aanpak: De "Twee-Witness" Methode

Brossard zegt: "Laten we die zelfmoord-paradox en die twijfelachtige aannames laten vallen. Laten we het op een andere manier doen."

Hij gebruikt een heel oud wiskundig probleem als basis: Hilbert's Tiende Probleem.

De vergelijking: Stel je voor dat je een enorme doos met puzzelstukjes hebt (een polynoom). De vraag is: "Kunnen we deze stukjes zo leggen dat ze perfect passen en een som van 0 geven?"
De ontdekking: Wiskundigen hebben bewezen dat er geen algemene regel is om te zeggen of zo'n puzzel ooit opgelost kan worden. Het is onmogelijk om een machine te bouwen die dit voor elke puzzel kan voorspellen.

3. Hoe werkt het nieuwe bewijs? (De Twee Getuigen)

Brossard gebruikt deze "onoplosbare puzzel" om Rice's Theorem te bewijzen. Hij doet dit met een slimme constructie die hij de "Twee-Witness" methode noemt.

Stel je voor dat je twee robots hebt, Robot A en Robot B.

Je geeft ze een wiskundige puzzel (de Diophantische polynoom).
Scenario 1: De puzzel is oplosbaar.
- Zodra de robots een oplossing vinden, verandert Robot A in een robot die nooit stopt (een eeuwig lopend programma).
- Robot B verandert in een robot die direct stopt (een programma dat klaar is).
- Als je nu een "detector" hebt die kan zien of een programma stopt, kan deze detector Robot A en Robot B onderscheiden!
Scenario 2: De puzzel is NIET oplosbaar.
- De robots zoeken eeuwig naar een oplossing, maar vinden er geen.
- Omdat ze nooit een oplossing vinden, blijven ze allebei in de zoekmodus hangen. Ze doen precies hetzelfde: ze lopen allebei oneindig door.
- Een detector kan ze niet van elkaar onderscheiden, omdat ze identiek zijn.

De conclusie:
Als er een machine was die kon zeggen of een programma een bepaalde eigenschap heeft (bijvoorbeeld "stopt het?"), dan zou die machine ook kunnen zeggen of de wiskundige puzzel oplosbaar is of niet.

Als de machine de robots kan onderscheiden -> De puzzel is oplosbaar.
Als de machine ze niet kan onderscheiden -> De puzzel is niet oplosbaar.

Maar we weten al dat er geen machine is die kan zeggen of zo'n puzzel oplosbaar is (dat is Hilbert's Tiende Probleem).
Dus: Er kan ook geen machine zijn die de eigenschappen van programma's kan voorspellen.

Waarom is dit belangrijk?

Geen "Of-Of" gedoe: Het oude bewijs vroeg: "Stopt dit programma wel of niet?" (een keuze die in strikte logica lastig is). Dit nieuwe bewijs zegt: "Kijk naar het verschil tussen twee robots." Als ze hetzelfde doen, is het antwoord hetzelfde. Geen keuze nodig.
Geen zelfreferentie: Het oude bewijs liet een programma naar zichzelf kijken (wat verwarrend is). Dit nieuwe bewijs laat robots kijken naar een wiskundige puzzel. Geen spiegel, gewoon puzzels.
Bouwkundig correct: Dit bewijs werkt zelfs in systemen die heel strikt zijn over wat "waar" is (intuïtionistische logica). Het is alsof je een brug bouwt zonder de "magische" steen van de uitgesloten midden. Je bouwt het puur met bakstenen die je echt hebt.

Samenvatting in één zin

In plaats van een programma te laten vechten met zichzelf om te bewijzen dat het onmogelijk is om alles te voorspellen, laat Brossard twee programma's samenwerken met een onoplosbare wiskundepuzzel: als de puzzel oplosbaar is, gedragen ze zich anders; als hij niet oplosbaar is, gedragen ze zich identiek. Omdat we de puzzel nooit kunnen oplossen, kunnen we ook die programma's nooit perfect voorspellen.

Het is een elegante, rustige manier om te bewijzen dat de computerwereld een grens heeft die we nooit kunnen overstijgen.

1. Het Probleem

De kern van het artikel is het bewijzen van Rice's Stelling en het Halting-probleem op een constructieve manier.

Rice's Stelling stelt dat geen enkele niet-triviale semantische eigenschap van programma's beslisbaar is.
Het Halting-probleem is een specifiek geval hiervan: er bestaat geen algoritme dat voor een willekeurig programma en invoer kan bepalen of het programma stopt.

Traditionele bewijzen voor deze stellingen zijn klassiek en vertrouwen op de Wet van het Uitgesloten Derde (Law of Excluded Middle - LEM). Ze gebruiken vaak:

Diagonalisatie: Het construeren van een programma dat zich tegenstrijdig gedraagt ten opzichte van een hypothetisch beslisalgoritme.
Zelfreferentie: Het gebruik van de Recursiestelling (fixed-point theorema) om een programma zijn eigen index te laten kennen.
Case-splits: Het aannemen dat een programma ofwel stopt ofwel divergeert, en het analyseren van de eigenschap $P(\bot)$ (waarbij $\bot$ een programma is dat altijd divergeert).

In intuïtionistische logica (gebruikt in bewijshulpmiddelen zoals Coq/Rocq) is LEM niet geldig. Klassieke bewijzen kunnen hierdoor niet direct worden geëxtraheerd naar geverifieerde code. Het doel van dit artikel is een bewijs te leveren dat volledig geldig is in intuïtionistische logica, zonder LEM, diagonalisatie of zelfreferentie.

2. Methodologie

De auteur presenteert een nieuw bewijs dat reductie gebruikt naar Hilbert's Tiende Probleem (de onbeslisbaarheid van Diophantische vergelijkingen), in plaats van naar het Halting-probleem.

De Kern van de Methode: De Twee-Witness Constructie
In plaats van één programma te construeren dat zich tegenstrijdig gedraagt (diagonalisatie), construeert de auteur voor elke Diophantische polynoom $D$ een paar programma's: $S^0_D$ en $S^1_D$ .

Input: Een niet-triviale semantische eigenschap $P$ met twee expliciete getuigen: $e_0$ (waarvoor $P(e_0)$ onwaar is) en $e_1$ (waarvoor $P(e_1)$ waar is).
Constructie:
- De programma's $S^b_D$ (waarbij $b \in \{0, 1\}$ ) zoeken systematisch naar een oplossing voor de polynoom $D(\vec{x}) = 0$ .
- Als $D$ een oplossing heeft: Zodra een oplossing wordt gevonden, gedraagt $S^1_D$ zich exact als $e_1$ en $S^0_D$ als $e_0$ .
- Als $D$ geen oplossing heeft: Beide programma's divergeren (lopen oneindig door) en zijn observationeel equivalent aan het divergente programma $\bot$ .
Het Argument:
- Stel er bestaat een beslisprogramma $Decide_P$ .
- Definieer het verschil $\delta_D = Decide_P(S^1_D) - Decide_P(S^0_D)$ .
- Geval 1 (Oplosbaar): Omdat $S^1_D \simeq e_1$ en $S^0_D \simeq e_0$ , geldt $P(S^1_D)$ en $\neg P(S^0_D)$ . Dus $\delta_D = 1 - 0 = 1$ .
- Geval 2 (Niet-oplosbaar): Omdat beide programma's divergeren ( $S^1_D \simeq S^0_D \simeq \bot$ ), moet een correcte beslisser voor semantische eigenschappen (die extensioneel is) hetzelfde resultaat geven voor beide. Dus $\delta_D = 0$ .
- Conclusie: De functie $D \mapsto \delta_D$ zou een beslisprogramma zijn voor Hilbert's Tiende Probleem. Omdat het MRDP-stelling (Matiyasevich-Robinson-Davis-Putnam) stelt dat Diophantische oplosbaarheid onbeslisbaar is, leidt dit tot een contradictie.

Belangrijke Constructieve Kenmerken:

Geen LEM op $P(\bot)$ : Het bewijs hoeft niet te weten of $P(\bot)$ waar of onwaar is. Als $D$ niet oplosbaar is, zijn $S^0_D$ en $S^1_D$ identiek, dus $P(S^0_D) \iff P(S^1_D)$ volgt uit extensionaliteit, ongeacht de waarde van $P(\bot)$ .
Geen Diagonalisatie: De programma's $S^b_D$ worden expliciet geconstrueerd op basis van de polynoom en een bit; er is geen zelfreferentie of fixed-point theorema nodig.
Implicaties in plaats van Disjunctie: Het bewijs wordt gestructureerd als twee aparte implicaties ( $D$ oplosbaar $\Rightarrow \delta_D=1$ en $D$ niet-oplosbaar $\Rightarrow \delta_D=0$ ), zonder de disjunctie "ofwel oplosbaar ofwel niet" te asserteren.

3. Belangrijkste Bijdragen

Constructief Bewijs van Rice's Stelling: Het eerste bewijs dat volledig geldig is in intuïtionistische logica, zonder klassieke axioma's (behalve de onbeslisbaarheid van Hilbert's Tiende Probleem zelf).
Eliminatie van Klassieke Technieken: Het bewijs doet geen beroep op diagonalisatie, zelfreferentie, of case-splitsen over het gedrag van divergente programma's.
Formalisatie in Rocq (Coq): De volledige theorie is geformaliseerd in de Rocq-proof assistant (voorheen Coq).
- Het gebruik maakt van een step-indexed model van berekening (programma's als functies van invoer en "brandstof" naar een optioneel resultaat).
- De formalisatie bevat 0 klassieke axioma's en 0 toegestane doelen (admitted goals).
- Het enige externe axioma is de onbeslisbaarheid van Hilbert's Tiende Probleem, die zelf constructief is bewezen in de bibliotheek coq-library-undecidability.
Afleiding van het Halting-probleem: Het onoplosbaarheid van het Halting-probleem volgt direct als een corollair (één regel code) door Rice's stelling toe te passen op de eigenschap "Terminates".

4. Resultaten

Rice's Stelling: Bewezen dat er geen beslisprogramma bestaat voor enige niet-triviale semantische eigenschap, binnen een intuïtionistisch kader.
Halting-probleem: Bewezen dat het Halting-probleem onbeslisbaar is, niet via een diagonaalargument, maar als een gevolg van de onbeslisbaarheid van Diophantische vergelijkingen.
Axioma-afhankelijkheid: De resultaten zijn "gesloten onder de globale context", wat betekent dat ze alleen afhankelijk zijn van de onbeslisbaarheid van Hilbert's Tiende Probleem en geen extra klassieke logica introduceren.
Praktische Implicatie: De constructie van de getuigenprogramma's ( $S^b_D$ ) is expliciet en computabel. Dit betekent dat de onbeslisbaarheid "inhoudelijk" is; het is niet slechts een abstracte negatieve stelling, maar een constructie die in theorie kan worden geëxtraheerd.

5. Significantie

Voor Constructieve Wiskunde en Type Theorie: Dit bewijs maakt het mogelijk om de onbeslisbaarheid van programmagebieden te internaliseren in systemen zoals Coq en Agda zonder toevlucht te nemen tot klassieke axioma's. Dit is cruciaal voor programma-extractie en geverifieerde software.
Reverse Wiskunde: Het draagt bij aan het in kaart brengen van welke niet-constructieve principes nodig zijn voor welke stellingen. Het toont aan dat Rice's stelling "zwakker" is dan vaak gedacht: het vereist geen volledige klassieke logica, maar slechts de onbeslisbaarheid van Diophantische vergelijkingen.
Nieuwe Reductiepad: Het keert de traditionele richting van bewijzen om. In plaats van "Halting $\to$ Rice", wordt nu "MRDP $\to$ Rice $\to$ Halting" bewezen. Dit biedt een nieuw perspectief op de hiërarchie van onbeslisbaarheid.
Diagonalisatie-vrij: Het toont aan dat diagonalisatie, hoewel historisch belangrijk, niet strikt noodzakelijk is voor het bewijzen van onbeslisbaarheid in een constructief kader.

Kortom, het artikel levert een fundamenteel nieuw, puur constructief bewijs voor twee van de bekendste stellingen in de theoretische informatica, ondersteund door een volledige mechanische verificatie.