Case study: solving P-99 with LPTP and an LLM

Stel je een wereld voor waarin computers niet alleen rigide, robotachtige instructies volgen, maar ook daadwerkelijk de rommelige, vage manier begrijpen waarop mensen problemen beschrijven. Dit is de grens van Artificiële Intelligentie, specifiek een tak genaamd Large Language Models (LLM's). Denk aan een LLM als een superintelligente, extreem goed gevleugelde student die bijna alles op het internet heeft gelezen. Als je het vraagt om een verhaal te schrijven, kan het dat; als je het vraagt om code te schrijven, kan het dat ook. Maar er is een addertje onder het gras: deze student is geneigd tot "hallucinaties", wat betekent dat het met veel zelfvertrouwen feiten kan verzinnen of code kan schrijven die er perfect uitziet, maar stiekem kapotgaat wanneer je probeert het uit te voeren.

Om dit op te lossen, gebruiken wetenschappers Formele Verificatie, wat lijkt op een superstrenge wiskundeleraar die elke stap van het huiswerk van een student controleert om te garanderen dat het logischerwijs onmogelijk is om fout te zitten. In de wereld van de informatica is er een beroemde set uitdagingen genaamd de 99 Prolog Problemen (of P-99). Deze zijn als de "gymworkouts" voor logische programmering, een stijl van coderen waarbij je beschrijft wat je wilt dat er gebeurt in plaats van hoe je dat stap voor stap moet doen. De grote vraag die onderzoekers stellen is: Kunnen we de AI-student de code laten schrijven op basis van een eenvoudige Engelse beschrijving, en vervolgens de wiskundeleraar de taak geven om direct te controleren of het daadwerkelijk correct is? Dit paper onderzoekt exact dat experiment, waarbij de creatieve vrijheid van AI wordt samengesmolten met de ijzeren veiligheid van formele logica.

---

Het Experiment: Een Codering-Duo met een Strenge Leraar

In dit onderzoek besloot een team van onderzoekers een nieuwe manier van werken te testen, genaamd "vibe-coding" gecombineerd met "vericoding." Stel je "vibe-coding" voor als het vragen aan een creatieve vriend om een boomhut voor je te bouwen op basis van een ruwe schets die je op een servet hebt getekend. Je zegt: "Ik wil een boomhut met een glijbaan en een geheime deur," en zij beginnen gewoon met bouwen. Het is snel en leuk, maar het resultaat kan wankel zijn. "Vericoding" is het tegenovergestelde: het is alsof je een architect inhuurt die blauwdrukken, stresstests en veiligheidsinspecties eist voordat er ook maar één spijker wordt geslagen.

De onderzoekers wilden zien of ze deze twee benaderingen konden combineren. Ze gebruikten een AI-model genaamd Claude (specifiek de Opus 4.6 versie) om als de creatieve bouwer te fungeren. Ze gaven het de eerste 33 problemen van de beroemde P-99 lijst, die geschreven zijn in eenvoudig, informeel Engels. Bijvoorbeeld, één probleem luidt simpelweg: "Vind het laatste element van een lijst."

De taak van de AI was om:

1. De Prolog-code te schrijven om het probleem op te lossen.
2. Een testbestand te schrijven om te controleren of de code werkt op voorbeelden.
3. Een formeel bewijs te schrijven om wiskundig te garanderen dat de code veilig is, correct is en altijd zal stoppen met draaien.

Om de bewijzen te controleren, gebruikten ze een tool genaamd LPTP (Logic Program Theorem Prover). Denk aan LPTP als de strenge wiskundeleraar die weigert "het ziet er goed uit" als antwoord te accepteren. Het eist een stapsgewijze logische afleiding voor elke bewering.

De Resultaten: Een Mix van Magie en Wiskunde

Het experiment was een succes, maar het was geen toverstaf. Het team slaagde erin om 33 van de 88 oefeningen (ongeveer 37,5%) op deze manier op te lossen. Dit is wat er achter de schermen gebeurde:

• Het Creatieve Deel (Vibe-Coding): De AI was verrassend goed in de initiële codering. Het schreef 58 logische procedures (de eigenlijke code) en 508 testgevallen in slechts enkele minuten per probleem. Het begreep de Engelse instructies en genereerde code die correct draaide.
• Het Strenge Deel (Vericoding): Hier begon het echte werk. De AI moest bewijzen dat de code correct was. Het genereerde 257 lemma's (kleine wiskundige feiten) en schreef een verbluffende 11.800 regels bewijs.
• De Menselijke Aanraking: De onderzoekers lieten de AI niet zomaar haar gang gaan. Ze controleerden handmatig elk bestand. Ze draaiden de tests, lazen de logische stellingen en voerden de bewijzen opnieuw uit met LPTP. Als de AI vastliep of een bewijs schreef dat geen zin maakte, grepen de mensen in om een hint te geven. Bijvoorbeeld, voor een probleem over het vinden van het laatste item in een lijst, moesten de mensen de AI vragen: "Hé, hoe verbindt dit met de append-functie?" om het te helpen de juiste bewijsvorming te formulagen.

De Belangrijkste Bevindingen

Het paper onthult een paar belangrijke zaken over deze nieuwe manier van werken:

1. AI wordt goed in "Vibe-Coding": De AI kon een vage Engelse beschrijving nemen en deze zeer snel omzetten in werkende Prolog-code. Het vermeed zelfs "onzuivere" trucjes die in de echte wereld vaak in Prolog worden gebruikt, en hield zich aan een strikte, logische stijl die de wiskundeleraar (LPTP) kon begrijpen.
2. AI heeft een duwtje nodig voor "Vericoding": Hoewel de AI de code gemakkelijk kon genereren, was het bewijzen waarom die correct was moeilijker. Voor complexe functionele eigenschappen (zoals bewijzen dat de code precies doet wat het moet doen), had de AI soms de menselijke onderzoekers nodig om de logica eerst in gewone mensentaal uit te leggen. Zodra de mensen een hint gaven, kon de AI dit formaliseren en bewijzen.
3. Het is nog geen "opgelost" probleem: Het team heeft niet alle 99 problemen opgelost. Sommige duurden slechts 15 minuten voor de AI (zoals het eenvoudige "laatste element"-probleem), terwijl andere enkele uren duurden (zoals het "priemfactorisatie"-probleem). De onderzoekers merken op dat de AI voor de moeilijkste problemen nog steeds moeite heeft om zelfstandig de juiste bewijsstrategieën te bedenken zonder menselijke begeleiding.

Een Blik in de Toekomst: De "MCP"-Connectie

Het paper beschrijft ook een nieuwe tool die ze aan het bouwen zijn, genaamd het Model Context Protocol (MCP). Momenteel communiceren de AI en de wiskundeleraar (LPTP) via bestanden en tekstdocumenten, wat een beetje is als het heen en weer sturen van brieven. De nieuwe MCP-tool is als het geven van een directe telefoonlijn aan hen. Dit stelt de AI in staat om de wiskundeleraar in realtime om hulp te vragen, haar eigen werk direct te controleren en fouten te herstellen zonder te wachten tot een mens ingrijpt. Ze testten dit met andere AI-modellen (zoals Gemini) en ontdekten dat hoewel sommige modellen de ideeën voor bewijzen konden genereren, alleen Claude in staat was om succesvol de geldige bewijzen te genereren die de strikte controles doorstonden.

De Kern van het Verhaal

Dit paper laat zien dat we een tijdperk binnenkomen waarin AI kan fungeren als een creatieve partner bij het schrijven van complexe, logische code, maar dat het nog steeds een menselijke "piloot" nodig heeft om door de moeilijkste delen te sturen. De AI kan de code schrijven en zelfs de wiskundige bewijzen opstellen, maar het raakt soms verdwaald in de details. Door de snelheid en creativiteit van de AI te combineren met een formele bewijschecker zoals LPTP, hebben de onderzoekers een systeem gecreëerd dat de fouten van de AI vangt voordat ze echte bugs worden. Het is nog geen volledig geautomatiseerde "fix-alles"-machine, maar het is een krachtig nieuw hulpmiddel dat het schrijven van betrouwbare software sneller en veiliger dan ooit maakt.