⚡ electrical engineering

Decentralized Decision-Making for Finite-State Systems over Finite Alphabets is Undecidable

Dit artikel toont aan dat gedecentraliseerde besluitvorming voor eindtoestandsystemen onbeslisbaar wordt onder eindige communicatiealfabetten wanneer niet-monotone fusierules zoals XOR worden gebruikt, wat contrasteert met klassieke resultaten die steunen op monotone regels.

Oorspronkelijke auteurs: Xiang Yin

Gepubliceerd 2026-06-17

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xiang Yin

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

Het Grote Plaatje: Een Spel van "Ja of Nee" met een Twist

Stel je een grote, complexe machine voor (zoals een fabrieksrobot of een verkeerssysteem) die wordt geobserveerd door twee aparte beveiligers. Deze beveiligers kunnen niet met elkaar praten; ze kunnen slechts delen van de machine zien.

Beveiliger 1 ziet een specifieke set lampjes.
Beveiliger 2 ziet een andere set lampjes.
De Baas zit in een controlekamer. Hij kan de machine niet direct zien. Hij ontvangt alleen een enkel "Ja" of "Nee" signaal van elke beveiliger.
Het Doel: De Baas moet weten of de machine op dit moment iets "Goeds" doet (de regels volgt) of iets "Slechts" (de regels overtreedt).

De Baas heeft een speciale regel voor het combineren van de antwoorden van de beveiligers. Hij gebruikt een logische poort genaamd XOR (Exclusive OR).

Als Beveiliger 1 "Ja" zegt en Beveiliger 2 "Nee", zegt de Baas "Goed."
Als Beveiliger 1 "Nee" zegt en Beveiliger 2 "Ja", zegt de Baas "Goed."
Als ze allebei "Ja" zeggen OF ze zeggen allebei "Nee", zegt de Baas "Slecht."

De Vraag: Kunnen we de beveiligers zo programmeren dat ze naar hun lampjes kijken en de juiste "Ja/Nee" signalen sturen, zodat de Baas altijd precies weet wanneer de machine het "Goede" ding doet?

De Belangrijkste Ontdekking van het Papier: De "Onmogelijke Puzzel"

Decennialang dachten onderzoekers dat als je de beveiligers eenvoudige regels gaf (zoals "Als een van jullie een rood licht ziet, zeg dan 'Stop'"), ze altijd een manier zouden kunnen vinden om de bevekers te programmeren om het probleem op te lossen.

Dit papier bewijst dat dit niet waar is.

De auteur, Xiang Yin, laat zien dat als je de XOR-regel gebruikt (waarbij de Baas nodig heeft dat de beveiligers verschillend antwoorden om "Goed" te zeggen), het mathematisch onmogelijk is om te weten of er een oplossing bestaat. Geen enkele computer, hoe krachtig ook, kan dit puzzelstukje voor elke mogelijke machine ooit oplossen.

De Analogie: Het "Woord Wissel" Spel

Hoe heeft de auteur dit bewezen? Hij heeft het machineprobleem omgezet in een beroemd, onoplosbaar woordspel genaamd het Thue Woord Probleem.

Stel je voor dat je een set magische regels hebt voor het wisselen van letters in een woord:

Regel 1: Je kunt "AB" wisselen met "BA".
Regel 2: Je kunt "C" wisselen met "BB".

Je begint met het woord "ABC".

Je kunt het veranderen in "BAC" (door AB te wisselen).
Dat kun je weer veranderen in "BABB" (door C te wisselen).

De Vraag: Kun je het woord "ABC" veranderen in het woord "BABB" met behulp van deze regels?

In de wereld van de wiskunde is dit een bekend onoplosbaar probleem. Er is geen algemene methode om "Ja" of "Nee" te beantwoorden voor elk mogelijk woord en elke mogelijke set regels.

De Verbinding:
De auteur bouwde een "machine" (het eindige-toestandsysteem) die exact werkt als dit woordspel:

De Identiteitstak (Identity Branch): De machine genereert woorden die hetzelfde lijken voor beide beveiligers. Dit dwingt de beveiligers om het met elkaar eens te zijn (hetzelfde signaal te sturen) zodat de Baas "Slecht" zegt (omdat XOR vereist dat ze het oneens zijn). Dit vestigt een basis van "waarheid".
De Herschrijf-tak (Rewrite Branch): De machine genereert woorden waarbij de beveiligers verschillende versies van hetzelfde woord zien (zoals "ABC" versus "BABB"). De regels van de machine dwingen de beveiligers om het weer met elkaar eens te zijn. Dit betekent dat de "waarheid" van het woord hetzelfde moet blijven na de wisseling.
De Gemerkte Tak (Marked Branch): De machine genereert een specifiek "Goed" scenario (het doelwoord). Hier heeft de Baas nodig dat de beveiligers het oneens zijn.

De Valstrik:
Als de twee woorden in het woordspel eigenlijk equivalent zijn (je kunt het ene woord in het andere veranderen), dwingen de regels van de machine de beveiligers om het met elkaar eens te zijn. Maar het "Goede" scenario vereist dat ze het oneens zijn. Dit creëert een tegenstrijdigheid.
Als ze niet equivalent zijn, kunnen de beveiligers worden geprogrammeerd om het oneens te zijn.

Omdat het "Woord Wissel" spel onoplosbaar is, is het "Machine Beveiliger" spel dat ook.

Waarom Gebeurt Dit? (De "Monotone" vs. "Chaotische" Regel)

Het papier legt uit dat eerdere succesvolle methoden vertrouwden op regels die Monotoon zijn (orde-behoudend).

AND/OR Regels: Als je meer informatie toevoegt, flipt het antwoord niet wild heen en weer. Het is als een commissie-stemming: als meer mensen voor stemmen, is de kans groter dat de uitslag "Ja" is. Deze structuur stelt computers in staat om een oplossing te vinden.
XOR Regel: Dit is Niet-Monotoon. Het is als de logica van "Steen, Papier, Schaar". Als beide beveiligers van mening veranderen, keert het resultaat volledig om. Dit gebrek aan een stabiele "orde" breekt de wiskundige instrumenten die we gewoonlijk gebruiken om deze problemen op te lossen.

Wat Over Andere Problemen?

Het papier laat zien dat deze "onmogelijkheid" niet alleen gaat over de Baas die probeert te raden of de machine werkt. Het verspreidt zich naar andere echte controleproblemen:

Gedecentraliseerde Controle: Kunnen we de beveiligers zo programmeren dat ze de machine stoppen van breken? (Nee, niet als we XOR gebruiken).
Foutdiagnose: Kunnen de beveiligers ons vertellen of een onderdeel kapot is gegaan? (Nee).
Foutprognose: Kunnen de beveiligers een defect voorspellen voordat het gebeurt? (Nee).

Samenvatting

De Opstelling: Twee bevegers houden een machine in de gaten en sturen binaire (Ja/Nee) signalen naar een Baas die een XOR regel gebruikt (heeft onenigheid nodig om "Goed" te zeggen).
Het Resultaat: Het is onbeslisbaar. Er is geen algoritme dat kan vertellen of er een set instructies voor de beveiligers bestaat om het probleem op te lossen.
De Reden: De XOR-regel vernietigt de wiskundige "structuur" (monotoniciteit) die computers normaal gesproken in staat stelt om deze puzzels op te lossen. Het probleem is wiskundig equivalent aan het onoplosbare "Thue Woord Probleem".
De Les: Zelfs met zeer eenvoudige, beperkte communicatie (slechts één bit van twee mensen), kan de keuze van hoe je hun antwoorden combineert (XOR) het hele systeem onmogelijk maken om te programmeren of te analyseren.

Technische Samenvatting: Gedecentraliseerde Besluitvorming voor Eindige-Toestandsystemen over Eindige Alfabetten is Onbeslisbaar

1. Probleemformulering

Dit artikel onderzoekt de fundamentele beslisbaarheid van gedecentraliseerde besluitvorming voor eindige-toestandsovergangssystemen (Discrete-Event Systemen of DES) onder strikte communicatiebeperkingen. Het probleem wordt geformuleerd binnen een algemene gedecentraliseerde observatiearchitectuur bestaande uit:

Een Plant: Een deterministische eindige-toestandsautomaat $G = (Q, \Sigma, f, q_0)$ .
Lokale Agenten: Twee agenten observeren de plant via disjuncte gebeurtenissenverzamelingen $\Sigma_{o,1}$ en $\Sigma_{o,2}$ via natuurlijke projecties $P_1$ en $P_2$ .
Communicatie: Elke agent genereert een lokaal beslissingssymbool uit een eindig alfabet $\Delta$ uitsluitend op basis van zijn observatiegeschiedenis.
Fusiecentrum: Een geheugenloos fusiecentrum past een vaste regel $F: \Delta \times \Delta \to \{0, 1\}$ toe op het paar lokale beslissingen om een globale binaire beslissing te produceren.

De kernvraag, de Gedecentraliseerde Observatieprobleem met Eindig Alfabet genoemd, is om te bepalen of er lokale beslissingskaarten $S_i: P_i(L(G)) \to \Delta$ bestaan zodanig dat het fusiecentrum exact een gegeven reguliere specificatielengte $K \subseteq L(G)$ kan reconstrueren. Specifiek moet voor alle $s \in L(G)$ de conditie $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ worden nagekomen.

2. Methodologie

De auteurs vestigen de onbeslisbaarheid van dit probleem door middel van een reductie van het Thue-woordprobleem, een klassiek onbeslisbaar probleem in de formele taaltheorie betreffende de equivalentie van twee woorden onder een eindige verzameling bidirectionele herschrijfregels.

Constructiestrategie:
Gegeven een instantie van het Thue-woordprobleem $(\Gamma, R, \alpha, \beta)$ , construeren de auteurs een specifieke gedecentraliseerde observatie-instantie $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ met de volgende eigenschappen:

Beperkte Architectuur: Het communicatiealfabet is binair ( $\Delta = \{0, 1\}$ ), en de fusierule is een vaste exclusive-or (XOR) operator ( $a \oplus b = 1 \iff a \neq b$ ).
Plantstructuur: De automaat $G$ $G$ wordt geconstrueerd met drie verschillende takken:
1. Identiteitstak: Genereert strings die willekeurige woorden $w \in \Gamma^*$ coderen als gepaarde sequenties. Deze tak dwingt de twee agenten om identieke beslissingswaarden toe te wijzen aan hetzelfde onderliggende woord $w$ (omdat de output 0 moet zijn voor niet-gemarkeerde strings, en $x \oplus y = 0 \implies x=y$ ). Dit maakt de definitie van een globale waarderingsfunctie $C(w)$ mogelijk.
2. Herschrijftakken: Voor elke herschrijfregel $(\ell_j, r_j) \in R$ genereert de plant strings waarbij Agent 1 een context observeert die $\ell_j$ bevat en Agent 2 observeert dezelfde context die $r_j$ bevat. Omdat deze strings niet-gemarkeerd zijn, dwingt de XOR-fusierule af dat $C(\dots \ell_j \dots) = C(\dots r_j \dots)$ . Dit dwingt af dat de waardering $C$ invariant is onder Thue-herschrijfstappen.
3. Gemarkeerde Tak: Genereert een unieke gemarkeerde string die de specifie fruit woorden $\alpha$ en $\beta$ codeert die respectievelijk door Agent 1 en Agent 2 worden geobserveerd. Voor een fusie-output van 1 (wat duidt op lidmaatschap in $K$ ) moeten de agenten verschillende waarden toewijzen: $C(\alpha) \neq C(\beta)$ .

Logische Reductie:
Het bestaan van geldige lokale beslissingskaarten impliceert het bestaan van een waardering $C$ die constant is op Thue-equivalentieklassen (vanwege de herschrijftakken) maar $\alpha$ en $\beta$ onderscheidt (vanwege de gemarkeerde tak). Een dergelijke waardering bestaat dan en slechts dan als $\alpha \not\equiv_R \beta$ . Aangezien het Thue-woordprobleem onbeslisbaar is, is ook het bepalen van het bestaan van dergelke kaarten onbeslisbaar.

3. Belangrijkste Bijdragen en Resultaten

Onbeslisbaarheid onder XOR: Het artikel bewijst dat het gedecentraliseerde observatieprobleem onbeslisbaar is, zelfs wanneer het beslissingsalfabet binair is en de fusierule vaststaat als XOR. Dit geldt voor een zeer beperkte informatiearchitectuur (twee agenten, eindig alfabet, geheugenloze fusie).
Rol van Monotoniciteit: De resultaten benadrukken dat de beslisbaarheid van bestaande architecturen (bijv. conjunctieve AND of disjunctieve OR regels) fundamenteel rust op de monotone, orde-preserverende aard van die fusierules. De XOR-regel is inherent niet-monotoon, wat de structurele eigenschappen doorbreekt die constructieve synthese en beslisbaarheid in klassieke omgevingen mogelijk maken.
Extensie naar Controle en Diagnose: De auteurs demonstreren dat het gedecentraliseerde observatieprobleem gereduceerd kan worden tot:
- Gedecentraliseerde Supervisory Control: Het bepalen van het bestaan van lokale supervisoren om een specificatie af te dwingen.
- Gedecentraliseerde Fault Diagnosis: Het bepalen van het bestaan van lokale diagnosers om fouten te detecteren met een begrensde vertraging en zonder valse alarmen.
- Gedecentraliseerde Fault Prognosis: Het bepalen van het bestaan van lokale prognosticatoren om fouten te voorspellen voordat ze optreden.
  Consequent worden al deze problemen getoond onbeslisbaar onder binaire beslissingsalfabetten en de XOR-fusierule.

4. Betekenis en Claims

Het artikel beweert een fundamentele beperking in gedecentraliseerde besluitvormingsarchitecturen bloot te leggen. Terwijl eerdere literatuur zich heeft gericht op het verrijken van beslissingsalfabetten of het ontwerpen van geavanceerde fusierules om de expressieve kracht te vergroten, laat dit werk zien dat de keuze van de fusierule de beslisbaarheid van het syntheseprobleem zelf fundamenteel kan veranderen.

De auteurs benadrukken dat hun resultaat strikt sterker is dan eerdere onbeslisbaarheidsresultaten (bijv. die met oneindige communicatiealfabetten) omdat de onbeslisbaarheid standhoudt zelfs wanneer het communicatiealfabet eindig (binair) is en de fusierule vaststaat. De intrinsieke bron van onbeslisbaarheid wordt geïdentificeerd als de gedecentraliseerde informatiestructuur die wordt geïnduceerd door onafhankelijke observaties die interageren met niet-monotone fusierules, in plaats van de grootte van het communicatiealfabet.

Het artikel sluit bescheiden af met de opmerking dat, hoewel het algemene probleem onbeslisbaar is, praktische toepassingen met begrensde geheugens bij lokale agenten de syntheseproblematiek beslisbaar kunnen maken via exhaustieve enumeratie, wat een richting biedt voor toekomstig onderzoek naar technieken voor begrensde synthese.