⚡ electrical engineering

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

Diese Arbeit zeigt auf, dass die dezentrale Entscheidungsfindung für endliche Zustandsautomaten unter Verwendung endlicher Kommunikationsalphabete bei nicht-monotonen Fusionsregeln wie XOR unentscheidbar wird, was im Gegensatz zu klassischen Ergebnissen steht, die auf monotonen Regeln beruhen.

Ursprüngliche Autoren: Xiang Yin

Veröffentlicht 2026-06-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xiang Yin

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

Das große Ganze: Ein Spiel aus „Ja oder Nein“ mit einem Twist

Stellen Sie sich eine große, komplexe Maschine vor (wie einen Fabrikroboter oder ein Verkehrssystem), die von zwei separaten Sicherheitswächtern beobachtet wird. Diese Wächter können nicht miteinander kommunizieren; sie können jeweils nur Teile der Maschine sehen.

Wächter 1 sieht einen bestimmten Satz von Lichtern.
Wächter 2 sieht einen anderen Satz von Lichtern.
Der Chef sitzt in einem Kontrollraum. Er kann die Maschine nicht direkt sehen. Er erhält nur ein einzelnes „Ja“ oder „Nein“-Signal von jedem Wächter.
Das Ziel: Der Chef muss wissen, ob die Maschine gerade etwas „Gutes“ tut (die Regeln befolgt) oder etwas „Schlechtes“ (die Regeln bricht).

Der Chef hat eine spezielle Regel, um die Antworten der Wächter zu kombinieren. Er verwendet ein Logikgatter namens XOR (Exklusives Oder).

Wenn Wächter 1 „Ja“ sagt und Wächter 2 „Nein“, sagt der Chef „Gut“.
Wenn Wächter 1 „Nein“ sagt und Wächter 2 „Ja“, sagt der Chef „Gut“.
Wenn beide „Ja“ sagen ODER beide „Nein“ sagen, sagt der Chef „Schlecht“.

Die Frage: Können wir die Wächter so programmieren, dass sie auf ihre Lichter schauen und die richtigen „Ja/Nein“-Signale senden, sodass der Chef immer genau weiß, wann die Maschine das „Gute“ tut?

Die Hauptentdeckung der Arbeit: Das „unlösbare Rätsel“

Jahrzehntelang dachten Forscher, dass man den Wächtern einfache Regeln geben könnte (wie „Wenn einer von euch ein rotes Licht sieht, sagt ‚Stopp‘“), und dass man dann immer eine Möglichkeit finden würde, die Wächter so zu programmieren, dass sie das Problem lösen.

Diese Arbeit beweist, dass das nicht wahr ist.

Der Autor, Xiang Yin, zeigt: Wenn man die XOR-Regel verwendet (bei der der Chef braucht, dass die Wächter uneinig sind, um „Gut“ zu sagen), wird es mathematisch unmöglich zu wissen, ob eine Lösung existiert. Kein Computer, egal wie leistungsstark, kann dieses Rätsel jemals für jede mögliche Maschine lösen.

Die Analogie: Das „Wort-Tausch-Spiel“

Wie hat der Autor dies bewiesen? Er hat das Maschinenproblem in ein berühmtes, unlösbares Wortspiel verwandelt: das Thue-Wortproblem.

Stellen Sie sich vor, Sie haben eine Reihe magischer Regeln für das Vertauschen von Buchstaben in einem Wort:

Regel 1: Sie können „AB“ durch „BA“ ersetzen.
Regel 2: Sie können „C“ durch „BB“ ersetzen.

Sie beginnen mit dem Wort „ABC“.

Sie können es in „BAC“ verwandeln (durch Vertauschen von AB).
Sie können das wiederum in „BABB“ verwandeln (durch Vertauschen von C).

Die Frage: Können Sie das Wort „ABC“ unter Verwendung dieser Regeln in das Wort „BABB“ verwandeln?

In der Welt der Mathematik ist dies ein bekanntes unlösbares Problem. Es gibt keine allgemeine Methode, um für jedes mögliche Wort und jede mögliche Menge an Regeln mit „Ja“ oder „Nein“ zu antworten.

Die Verbindung:
Der Autor hat eine „Maschine“ (das endliche Zustandsystem) gebaut, die exakt wie dieses Wortspiel funktioniert.

Der Identitäts-Zweig: Die Maschine erzeugt Wörter, die für beide Wächter gleich aussehen. Dies zwingt die Wächter dazu, sich einig zu sein (das gleiche Signal zu senden), damit der Chef „Schlecht“ sagt (da XOR eine Uneinigkeit benötigt). Dies etabliert eine Basis-„Wahrheit“.
Der Umschreib-Zweig: Die Maschine erzeugt Wörter, bei denen die Wächter verschiedene Versionen desselben Wortes sehen (wie „ABC“ vs. „BABB“). Die Regeln der Maschine zwingen die Wächter dazu, sich erneut einig zu sein. Das bedeutet, dass die „Wahrheit“ des Wortes auch nach dem Tausch gleich bleiben muss.
Der Markierte-Zweig: Die Maschine erzeugt ein spezifisches „Gutes“ Szenario (das Zielwort). Hier muss der Chef, dass die Wächter uneinig sind.

Die Falle:
Wenn die beiden Wörter im Wortspiel tatsächlich äquivalent sind (man kann also das eine in das andere verwandeln), zwingen die Regeln die Wächter dazu, sich einig zu sein. Aber das „Gute“ Szenario erfordert jedoch, dass sie uneinig sind. Dies führt zu einem Widerspruch.
Wenn sie nicht äquivalent sind, können die Wächter so programmiert werden, dass sie uneinig sind.

Da das „Wort-Tausch-Spiel“ unlösbar ist, ist auch das „Maschinen-Wächter-Spiel“ unlösbar.

Warum passiert das? (Die „monotone“ vs. „chaotische“ Regel)

Die Arbeit erklärt, dass bisherige erfolgreiche Methoden auf Regeln basierten, die monoton (ordnungserhaltend) sind.

AND/OR-Regeln: Wenn man mehr Informationen hinzufügt, springt die Antwort nicht wild hin und her. Es ist wie bei einer Ausschussabstimmung: Wenn mehr Leute mit „Ja“ stimmen, ist das Ergebnis wahrscheinlicher auch „Ja“. Diese Struktur ermöglicht es Computern, eine Lösung zu finden.
XOR-Regel: Diese ist nicht-monoton. Es ist wie die Logik von „Schere, Stein, Papier“. Wenn beide Wächter ihre Meinung ändern, kippt das Ergebnis komplett um. Dieser Mangel an einer stabilen „Ordnung“ zerstört die mathematischen Werkzeuge, die wir normalerweise nutzen, um solche Probleme zu lösen.

Was ist mit anderen Problemen?

Die Arbeit zeigt, dass diese „Unmöglichkeit“ nicht nur beim Raten des Chefs geht, ob die Maschine funktioniert. Sie überträgt sich auf andere reale Kontrollprobleme:

Dezentrale Steuerung: Können wir die Wächter so programmieren, dass sie die Maschine am Kaputtgehen hindern? (Nein, nicht wenn wir XOR verwenden).
Fehlerdiagnose: Können die Wächter uns sagen, ob ein Teil defekt ist? (Nein).
Fehlprognose: Können die Wächter einen Defekt vorhersagen, bevor er eintritt? (Nein).

Zusammenfassung

Das Setup: Zwei Wächter beobachten eine Maschine und senden binäre (Ja/Nein) Signale an einen Chef, der eine XOR-Regel verwendet (braucht Uneinigkeit, um „Gut“ zu sagen).
Das Ergebnis: Es ist unentscheidbar. Es gibt keinen Algorithmus, der feststellen kann, ob eine Menge von Anweisungen für die Wächter existiert, um das Problem zu lösen.
Der Grund: Die XOR-Regel zerstört die mathematische „Struktur“ (Monotonie), die es Computern normalerweise ermöglicht, diese Rätsel zu lösen. Das Problem ist mathematisch äquivalent zum unlösbaren „Thue-Wortproblem“.
Die Erkenntnis: Selbst mit sehr einfacher, eingeschränkter Kommunikation (nur ein Bit von zwei Personen) kann die Wahl der Art und Weise, wie man ihre Antworten kombiniert (XOR), das gesamte System unprogrammierbar oder unanalysierbar machen.

Technische Zusammenfassung: Die dezentrale Entscheidungsfindung für endliche Zustandsysteme über endlichen Alphabeten ist unentscheidbar

1. Problemformulierung

Diese Arbeit untersucht die grundlegende Entscheidbarkeit der dezentralen Entscheidungsfindung für endliche Zustandsübergangssysteme (Discrete-Event Systeme oder DES) unter strengen Kommunikationsbeschränkungen. Das Problem wird in einer allgemeinen dezentralen Beobachtungsarchitektur formuliert, die Folgendes umfasst:

Eine Anlage (Plant): Ein deterministischer endlicher Automat $G = (Q, \Sigma, f, q_0)$ .
Lokale Agenten: Zwei Agenten beobachten die Anlage durch disjunkte Ereignismengen $\Sigma_{o,1}$ und $\Sigma_{o,2}$ mittels natürlicher Projektionen $P_1$ und $P_2$ .
Kommunikation: Jeder Agent generiert ein lokales Entscheidungssymbol aus einem endlichen Alphabet $\Delta$ , das ausschließlich auf seiner Beobachtungshistorie basiert.
Fusionszentrum: Ein gedächtnisloses Fusionszentrum wendet eine feste Regel $F: \Delta \times \Delta \to \{0, 1\}$ auf das Paar der lokalen Entscheidungen an, um eine globale binäre Entscheidung zu erzeugen.

Die Kernfrage, bezeichnet als das Dezentrale Beobachtungsproblem mit endlichem Alphabet, ist die Frage, ob es lokale Entscheidungsabbildungen $S_i: P_i(L(G)) \to \Delta$ gibt, so dass das Fusionszentrum eine gegebene reguläre Spezifikationssprache $K \subseteq L(G)$ exakt rekonstruieren kann. Konkret muss für alle $s \in L(G)$ die Bedingung $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ erfüllt sein.

2. Methodik

Die Autoren begründen die Unentscheidbarkeit dieses Problems durch eine Reduktion auf das Thue-Wortproblem, ein klassisches unentscheidbares Problem der formalen Sprachtheorie, das sich mit der Äquivalenz zweier Wörter unter einer endlichen Menge von bidirektionalen Umschreibungsregeln befasst.

Konstruktionsstrategie:
Gegeben sei eine Instanz des Thue-Wortproblems $(\Gamma, R, \alpha, \beta)$ . Die Autoren konstruieren eine spezifische Instanz des dezentralen Beobachtungsproblems $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ mit den folgenden Eigenschaften:

Eingeschränkte Architektur: Das Kommunikationsalphabet ist binär ( $\Delta = \{0, 1\}$ ) und die Fusionsregel ist auf den Exklusiv-Oder (XOR)-Operator festgelegt ( $a \oplus b = 1 \iff a \neq b$ ).
Struktur der Anlage: Der Automat $G$ $G$ wird mit drei distinkten Zweigen konstruiert:
1. Identitätszweig: Erzeugt Wörter, die beliebige Wörter $w \in \Gamma^*$ als gepaarte Sequenzen kodieren. Dieser Zweig erzwingt, dass die beiden Agenten identische Entscheidungswerte für dasselbe zugrunde liegende Wort $w$ zuweisen (da die Ausgabe 0 für nicht markierte Strings sein muss, und $x \oplus y = 0 \implies x=y$ ). Dies ermöglicht die Definition einer globalen Bewertungsfunktion $C(w)$ .
2. Umschreibzweige: Für jede Umschreibungsregel $(\ell_j, r_j) \in R$ erzeugt die Anlage Strings, bei denen Agent 1 einen Kontext beobachtet, der $\ell_j$ enthält, und Agent 2 denselben Kontext, der $r_j$ enthält. Da diese Strings nicht markiert sind, erzwingt die XOR-Fusionsregel $C(\dots \ell_j \dots) = C(\dots r_j \dots)$ . Dies erzwingt, dass die Bewertung $C$ unter Thue-Umschreibungsschritten invariant bleibt.
3. Markierter Zweig: Erzeugt einen einzigartigen markierten String, der die spezifischen Wörter $\alpha$ und $\beta$ kodiert, die von den Agenten 1 und 2 jeweils beobachtet werden. Damit die Fusionsausgabe 1 ist (was die Zugehörigkeit zu $K$ anzeigt), müssen die Agenten unterschiedliche Werte zuweisen: $C(\alpha) \neq C(\beta)$ .

Logische Reduktion:
Die Existenz gültiger lokaler Entscheidungsabbildungen impliziert die Existenz einer Bewertung $C$ , die aufgrund der Umschreibzweige konstant auf Thue-Äquivalenzklassen ist, aber $\alpha$ und $\beta$ unterscheidet (aufgrund des markierten Zweigs). Eine solche Bewertung existiert genau dann, wenn $\alpha \not\equiv_R \beta$ . Da das Thue-Wortproblem unentscheidbar ist, ist auch die Bestimmung der Existenz solcher Abbildungen unentscheidbar.

3. Zentrale Beiträge und Ergebnisse

Unentscheidbarkeit unter XOR: Die Arbeit beweist, dass das dezentrale Beobachtungsproblem unentscheidbar ist, selbst wenn das Entscheidungsalphabet binär ist und die Fusionsregel auf XOR festgelegt ist. Dies gilt für eine hochgradig eingeschränkte Informationsarchitektur (zwei Agenten, endliches Alphabet, gedächtnisloses Fusionszentrum).
Rolle der Monotonie: Die Ergebnisse verdeutlichen, dass die Entscheidbarkeit bestehender Architekturen (z. B. konjunktive AND- oder disjunktive OR-Regeln) fundamental auf der monotonen, ordnungserhaltenden Natur dieser Fusionsregeln beruht. Die XOR-Regel ist inhärent nicht-monoton und bricht die strukturellen Eigenschaften, die in klassischen Settings die konstruktive Synthese und Entscheidbarkeit ermöglichen.
Erweiterung auf Kontrolle und Diagnose: Die Autoren zeigen, dass das dezentrale Beobachtungsproblem auf folgende Probleme reduziert werden kann:
- Dezentrale supervisory Kontrolle: Bestimmung der Existenz lokaler Supervisoren zur Durchsetzung einer Spezifikation.
- Dezentrale Fehlerdiagnose: Bestimmung der Existenz lokaler Diagnosierer zur Erkennung von Fehlern mit begrenzter Verzögerung und ohne Fehlalarme.
- Dezentrale Fehlerprognose: Bestimmung der Existenz lokaler Prognostiker zur Vorhersage von Fehlern vor deren Auftreten.
  Folglich sind alle diese Probleme unter binären Entscheidungsalphabeten und der XOR-Fusionsregel als unentscheidbar erwiesen.

4. Bedeutung und Behauptungen

Die Arbeit behauptet, eine fundamentale Einschränkung in dezentralen Entscheidungsarchitekturen aufzuzeigen. Während die bisherige Literatur darauf fokussiert war, die Ausdrucksstärke durch Anreicherung der Entscheidungsalphabete oder durch komplexere Fusionsregeln zu erhöhen, zeigt diese Arbeit, dass die Wahl der Fusionsregel die Entscheidbarkeit des Syntheseproblems selbst fundamental verändern kann.

Die Autoren betonen, dass ihr Ergebnis strenger ist als frühere Unentscheidbarkeitsergebnisse (z. B. solche, die unendliche Kommunikationsalphabete involvieren), da die Unentscheidbarkeit selbst dann bestehen bleibt, wenn das Kommunikationsalphabet endlich (binär) ist und die Fusionsregel fest vorgegeben ist. Die intrinsische Quelle der Unentscheidbarkeit wird in der dezentralen Informationsstruktur identifiziert, die durch unabhängige Beobachtungen in Interaktion mit nicht-monotonen Fusionsregeln induziert wird, und nicht in der Größe des Kommunikationsalphabets.

Die Arbeit schließt bescheiden mit dem Hinweis, dass praktische Anwendungen mit begrenztem Speicher bei den lokalen Agenten das Syntheseproblem mittels erschöpfender Enumeration entscheidbar machen könnten, was einen Weg für zukünftige Forschungen zu Techniken der begrenzten Synthese (Bounded-Synthesis) eröffnet.