💻 computer science

GPU-Accelerated Search and Certification of Bounded Indistinguishability in Finite Kripke Semantics

Dit artikel presenteert een door GPU versneld framework dat eindige Kripke-semantiek codeert als bitmasks om exhaustieve modale formule-evaluatie en tegenmodel-certificering op massale schaal uit te voeren, waarbij nauwe grenzen op weerlegbaarheid worden onthuld, semantische mirages worden gesynthetiseerd en graphics-ondersteunde semantische exploratie wordt mogelijk gemaakt.

Oorspronkelijke auteurs: Faruk Alpay, Baris Basaran

Gepubliceerd 2026-06-16

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Faruk Alpay, Baris Basaran

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 probeert uit te zoeken of twee verschillende sets instructies (genaamd "formules") eigenlijk hetzelfde zijn. In de wereld van de logica zijn twee instructies soms compleet verschillend, maar geven ze exact hetzelfde resultaat in elke kleine situatie die je ook kunt bedenken. De grote vraag is: Hoe groot moet de situatie worden voordat je eindelijk een verschil ziet?

Dit artikel is als een enorme, razendsnelle experimentele opzet, ontworpen om die vraag te beantwoorden met behulp van een super-snelle computerchip (een GPU). Hier is de onderverdeling van wat ze hebben gedaan en gevonden, met behulp van eenvoudige analogieën.

1. Het Probleem: De "Kleine Wereld" Valstrik

In de logica is er een regel die zegt dat als een instructie fout is, je dat kunt bewijzen met een "tegenvoorbeeld" — een specifiek scenario waarin het faalt. Meestal weten we dat deze scenario's bestaan, maar de wiskunde zegt dat ze onvoorstelbaar groot kunnen zijn (zoals een stad met miljarden huizen).

De onderzoekers vroegen zich af: Hebben we echt een stad nodig om een fout te vinden, of kunnen we die vinden in een klein dorpje? En nog belangrijker: Als twee instructies in een dorpje identiek lijken, hoe groot moet de stad dan zijn voordat ze anders gaan handelen?

2. Het Gereedschap: De "Bitmask" Super-Scanner

Om dit te testen, bouwden ze een speciale scanner. In plaats van één scenario tegelijk te controleren (zoals een mens die een boek leest), veranderden ze de hele wereld van mogelijkheden in integers (getallen).

De Analogie: Stel je een rij lichtschakelaars voor. Als een schakelaar "aan" staat, is een conditie waar; als hij "uit" staat, is het onwaar.
De Truc: Ze stopten duizenden van deze schakelaars in één enkel getal. Vervolgens gebruikten ze de grafische kaart van de computer (de GPU) om deze schakelaars voor miljoenen verschillende "werelden" tegelijkertijd om te zetten.
Het Resultaat: Ze konden 163 biljoen (1,63 × 10¹⁴) verschillende scenario's controleren in slechts 45 minuten. Dat is alsof je elke mogelijke schudvolgorde van een kaartspel controleert in de tijd die het kost om een kopje koffie te zetten.

3. Bevinding 1: Kleine Fouten Komen Veel Voor

Ze testten duizenden eenvoudige logische formules.

De Bevinding: De meeste formules die "fout" zijn (ongeldig), falen heel snel. Sterker nog, voor het overgrote deel van hen heb je slechts een wereld met één of twee "kamers" (werelden) nodig om te bewijzen dat ze fout zijn.
De Metafoor: De oude wiskundeboeken zeiden: "Om te bewijzen dat dit fout is, heb je misschien een landhuis met 128 kamers nodig." De onderzoekers ontdekten dat je in de praktijk bijna altijd alleen een kast (1 of 2 kamers) nodig hebt om de fout te vangen. De schatting van het "landhuis" was veel te pessimistisch.

4. Bevinding 2: De "Semantische Mirage" (De Tricky Tweelingen)

Het meest opwindende deel was het vinden van twee formules die ononderscheidbaar zijn voor een lange tijd.

De Analogie: Stel je twee tweelingen voor, Alpha-2 en Alpha-3. Als je hen in een kamer zet met 1, 2, 3, 4 of zelfs 5 mensen, gedragen ze zich exact hetzelfde. Je kunt hen niet van elkaar onderscheiden.
De Doorbraak: De onderzoekers ontdekten dat deze tweelingen uiteindelijk wel degelijk anders gaan handelen, maar pas wanneer je ze in een kamer met 6 mensen plaatst.
Het Bewijs: Ze hebben dit niet alleen geraden. Ze bouwden een specifieke kamer voor 6 personen (een "tegenmodel") en bewezen wiskundig dat dit de kleinste mogelijke kamer is waar de tweelingen uiteenlopen. Voorheen wist niemand precies waar de lijn getrokken was.

5. Bevinding 3: De "Kaart" versus de "Zoekmachine"

Ze probeerden deze logische formules ook te visualiseren op een 2D-kaart (zoals een scatterplot) om te zien of mensen het verschil simpelweg door naar de afbeelding te kijken zouden kunnen herkennen.

Het Resultaat: De kaart was een rommeltje. Het was alsof je probeerde een specifieke naald in een hooiberg te vinden waarbij 99% van de naalden op elkaar gestapeld lag.
De Conclusie: De kaart is goed voor het genereren van ideeën (het vinden van kandidaten), maar het is geen ontdekkingsmachine. Je kunt niet gewoon naar de afbeelding kijken en zeggen: "Ah, daar zit het verschil!" Je hebt nog steeds de super-snelle computer nodig om de specifieke kandidaten die de kaart suggereert te controleren. De computer is de rechter; de kaart is slechts een suggestiebox.

6. Het "Certificaat" Systeem

Om er zeker van te zijn dat de super-snelle computer geen fout maakte (omdat hij zo snel is dat hij een stap zou kunnen overslaan), bouwden ze een apart, langzamer, maar zeer zorgvuldig "scheidsrechter"-programma.

Hoe het werkt: De snelle computer vindt een potentiële fout en overhandigt een "certificaat" (een briefje met: "Hier is de formule, hier is de wereld, hier is het bewijs").
De Controle: De langzame scheidsrechter leest het certificaat en zegt: "Ja, dit is correct."
Waarom het belangrijk is: Dit betekent dat de resultaten 100% betrouwbaar zijn. Ze kregen niet alleen een snel antwoord; ze kregen een geverifieerd antwoord.

Samenvatting

Het artikel gaat over het gebruik van een super-snelle grafische kaart om logische regels in kleine werelden uitputtend te testen. Ze ontdekten dat:

De meeste logische fouten worden gevangen in zeer kleine werelden (1 of 2 kamers).
Ze vonden een specifiek paar logische regels die identiek lijken tot je een wereld met 6 kamers bereikt, en ze bewezen dat dit exact het punt is waarop ze uiteenlopen.
Visuele kaarten helpen je om te zien waar je moet zoeken, maar je hebt nog steeds de computer nodig om te bevestigen wat je ziet.

Het is een verhaal over het gebruik van brute kracht (alles controleren) gecombineerd met slimme wiskunde om het exacte moment te vinden waarop twee dingen ophouden hetzelfde te zijn.

Technische Samenvatting: GPU-versnelde Zoektocht en Certificering van Begrensde Ononderscheidbaarheid in Eindige Kripke-semantiek

Probleemstelling
Het artikel behandelt twee fundamentele vragen met betrekking tot modale logica en eindige modeltheorie die weliswaar beslisbaar zijn, maar computationeel kostbaar:

Minimale Tegenmodelgrootte: Hoe groot zijn de minimale tegenmodellen in de praktijk voor ongeldige modale formules, vergeleken met de standaard exponentiële grenzen die worden geboden door de Eindige Model-Eigenschap (FMP) en filtratie?
Begrensde Ononderscheidbaarheid: Hoe groot moet een eindig model zijn voordat het twee formules kan onderscheiden die op alle kleinere modellen gelijk lijken te zijn? De auteurs definiëren een paar formules als k-ononderscheidbaar als ze overeenstemmen op alle frames van grootte $\le k$ , maar uiteenlopen op een frame van grootte $k+1$ .

Hoewel standaardtechnieken zoals BDD-gebaseerde symbolische modelcontrole grote toestandsruimten comprimeren voor een enkele formule, richt dit werk zich op het tegenovergestelde regime: een volledige census van veel formules tegen veel kleine frames tegelijkertijd.

Methodologie
De auteurs maken gebruik van de bitwijze aard van eindige Kripke-evaluatie om massale parallellisatie op GPU's mogelijk te maken.

Bitmask-codering: Werelden worden gecodeerd als integers, en waarderingen als bitmasks. Booleaanse connectieven mappen naar bitwijze operaties, terwijl modale operatoren ( $\Box$ en $\Diamond$ ) worden gereduceerd tot bevatting- en doorsnede-testen op opvolger-masks (Lemma 1). Dit elimineert de noodzaak om de $(frame \times valuation)$ waarheidstensor te materialiseren.
Fused CUDA Kernel: Een enkele kernel evalueert een hele corpus aan formules tegen alle frames van een vaste grootte in één pass. Threads worden toegewezen aan frames, waarbij ze door waarderingen itereren via loop-indices (om waarderingsarrays te vermijden) en resultaten reduceren met behulp van shared memory om atomische congestie te minimaliseren.
Verificatie-architectuur: Het systeem hanteert een "fast search, slow check"-paradigma. De GPU voert de uitputtende enumeratie uit, terwijl een aparte, transparante recursieve CPU-evaluator (onafhankelijk van de bitmask-engine) elk gerapporteerd tegenmodel verifieert. Dit garandeert dat de resultaten betrouwbaar zijn, ongeacht de implementatiedetails van de accelerator.
Actieve Synthese: Naast passieve enumeratie gebruiken de auteurs een actief syntheseprotocol om kandidaat-formuleparen te genereren (bijv. $(\Box\Diamond)^m\top$ ) en zoekt naar "semantische mirages" (ononderscheidbare paren) met behulp van adversariële framegeneratie (Erdős–Rényi, SCC-bottlenecks, etc.) en SAT-solvers voor minimaliteitsbewijzen.
Representatie-gestuurde Retrieval: Het artikel construeert een "semantische atlas" (een dichtheidsmatrix van falingsprofielen) en evalueert diverse dimensionaliteitsreductietechnieken (PCA, UMAP, spectraal) voor kandidaat-retrieval. Cruciaal is dat de visualisaties worden behandeld als interfaces voor kandidaat-generatie, niet als zelfstandige ontdekkingsmechanismen; elke kandidaat wordt opnieuw geverifieerd via uitputtende zoektocht.

Belangrijkste Bijdragen en Resultaten

Correctheid en Complexiteit: De auteurs leveren een correctheidsbewijs voor de bitmask-evaluator (Theorema 1) en een complexiteitsanalyse die aantoont dat de aanpak het opslaan van de waarheidstensor vermijdt (Propositie 1). Alle 20.990 gegenereerde certificaten werden onafhankelijk geverifieerd.
Kleine Minimale Tegenmodellen: In een corpus van 5.624 constante-vrije formules (tot 7 knopen, 2 variabelen) stelde de studie vast dat minimale tegenmodellen verrassend klein zijn.
- Elke weerlegbare formule in de logica K wordt weerlegd op maximaal 2 werelden (Propositie 3).
- De standaard filtratie-grens ( $2^{|Sub(\phi)|}$ ) is empirisch ruim; voor 7-knopen formules suggereert de grens tot wel 128 werelden, maar de maximaal geobserveerde waarde was 2 (Corollary 1).
Synthese van Begrensde Ononderscheidbaarheid: De auteurs hebben succesvol een gecertificeerd 5-ononderscheidbaar paar gesynthetiseerd ( $\alpha_2 = (\Box\Diamond)^2\top$ $α_{2} = (□◊)^{2} ⊤$ en $\alpha_3 = (\Box\Diamond)^3\top$ $α_{3} = (□◊)^{3} ⊤$ ). Deze formules komen overeen op alle frames van grootte $\le 5$ $\leq 5$ , maar worden gescheiden door een specifiek 6-werelden pad (Propositie 5).
- Deze separatie werd bevestigd door zowel uitputtende GPU-enumeratie als symbolische SAT-bewijzen (Tabel 3).
- Adversariële frame-synthese produceerde 90 geverifieerde separaties, waarvan er 78 niet-template waren (d.w.z. geen eenvoudige paden of cycli).
Systeemprestaties:
- De gefuseerde H100-implementatie bereikte een duurzame snelheid van 60,2 miljard evaluaties per seconde (1,63 $\times$ 10 $^{14}$ totale evaluaties in 45 minuten).
- Dit was 47,1 $\times$ sneller dan een bit-parallel OpenMP CPU en 7,06 $\times$ sneller dan een expliciete AVX-512 CPU-baseline op vergelijkbare workloads.
- Hardware-kalibratie bereikte 18,87 source-level uint32 TOPS met 98,3% gemiddelde NVML busy time.
Representatie en Retrieval:
- Bij een retrieval-taak over 5,4 miljoen kandidaat-paren presteerden ruwe hoog-dimensionale features het best bij krappe buurt-budgetten ( $k=16$ ), terwijl een 2D PCA-atlas het best presteerde bij bredere budgetten ( $k=1024$ ).
- De auteurs benadrukken echter dat 2D-visualisaties lijden onder extreme clutter (98,6% van de punten deelt een bin bij een schaal van 100k) en niet als zelfstandige ontdekkingsinstrumenten dienen. De pijplijn vertrouwt op representatie-gestuurde voorstellen gevolgd door uitputtende verificatie.
Herstel van Correspondentie: De engine slaagde erin de eerste-orde framecondities te herstellen voor alle Sahlqvist-axioma's (T, D, 4, 5, B, etc.) en identificeerde correct dat het McKinsey-axioma geen eerste-orde correspondent heeft in de geteste bibliotheek, wat de systeemvaliditeit tegen gevestigde theorie bevestigt.

Betekenis en Omvang
Het artikel claimt significantie niet als een nieuwe beslissingsprocedure voor algemene modale logica (die PSPACE-compleet blijft), maar als een reproduceerbaar protocol voor het verkennen van de "kleine-model-regime" en de grenzen van ononderscheidbaarheid.

Bescheidenheid van Claims: De auteurs verklaren expliciet dat hun resultaten begrensd zijn. De census beslist alleen over de geldigheid van formules waarbij de FMP-grens binnen de gezochte grootte valt (tot 5 werelden). Claims over formules die deze range overleven, zijn schattingen of begrensde overlevers, geen stellingen.
Ontdekking versus Verificatie: Het artikel maakt onderscheid tussen het genereren van kandidaten (via synthese of visuele atlas) en het certificeren ervan. De "ontdekking" van het 5-ononderscheidbare paar is een resultaat van actieve synthese en uitputtende verificatie, niet louter visuele inspectie.
Complementariteit: Het werk wordt gepresenteerd als complementair aan symbolische modelcontrole (BDDs/SAT). Terwijl symbolische methoden één grote toestandsruimte comprimeren, scant deze aanpak expliciet vele kleine modellen tegen vele formules, een regime waarin symbolische methoden mogelijk niet optimaal zijn.

Samenvattend demonstreert het artikel dat GPU-versnelde bitwijze evaluatie een uitputtende census van kleine Kripke-modellen mogelijk maakt, waarbij wordt aangetoond dat minimale tegenmodellen vaak veel kleiner zijn dan theoretische grenzen suggereren, en biedt het een rigoureus kader voor de synthese en certificering van begrensde ononderscheidbaarheid in modale logica.