Dependent Directed Wiring Diagrams for Composing Instantaneous Systems

Dit paper introduceert een operad van afhankelijke gerichte bedradingsdiagrammen om onmiddellijke systemen, zoals Mealy-machines en voorraad-stroomdiagrammen, te componeren door cycli in bedrading en directe input-afhankelijkheid van outputs te vermijden.

De kern

Hier is een uitleg van het paper "Dependent Directed Wiring Diagrams for Composing Instantaneous Systems", vertaald naar begrijpelijk Nederlands met behulp van alledaagse analogieën.

De Kern: Hoe bouw je complexe systemen zonder dat ze in de war raken?

Stel je voor dat je een enorme stad bouwt. Je hebt duizenden kleine onderdelen: verkeerslichten, waterpompen, energiecentrales en scholen. Elk van deze onderdelen heeft ingangen (zoals stroom of water) en uitgangen (zoals licht of gedroogde kleding).

In de wereld van wiskunde en systeemtheorie noemen we deze onderdelen machines. De grote vraag is: Hoe kun je deze machines aan elkaar koppelen om één groot, werkend systeem te maken?

De auteurs van dit paper, Keri D'Angelo en Sophie Libkind, hebben een nieuwe manier bedacht om dit te doen, vooral voor machines die direct reageren op wat er binnenkomt.

---

1. Het oude verhaal: De "Moore Machine" (De Geduldige Buurman)

Stel je een oude, geduldige buurman voor.

• Hij krijgt een brief (de input).
• Hij leest de brief, denkt er een dag over na (de staat of state), en schrijft de volgende dag pas een antwoord (de output).
• Omdat hij eerst denkt voordat hij antwoordt, kan hij zijn antwoord aan je geven terwijl jij nog een nieuwe brief krijgt. Er is geen chaos.

In de wiskunde heten deze "geduldige" machines Moore-machines. Ze zijn makkelijk te combineren. Je kunt de uitgang van de ene machine direct aan de ingang van de andere hangen, en het werkt altijd.

2. Het nieuwe probleem: De "Mealy Machine" (De Snelle Buurman)

Nu stel je je een heel snelle, impulsieve buurman voor.

• Hij krijgt een brief.
• Hij schrijft direct een antwoord, terwijl hij de brief nog in zijn hand heeft. Zijn antwoord hangt af van de brief en wat hij al wist.
• Dit is een Mealy-machine.

Het probleem: Wat gebeurt er als je twee van deze snelle buurmannen aan elkaar koppelt?
Stel, Buurman A zegt: "Mijn antwoord hangt af van wat jij zegt." En Buurman B zegt: "Mijn antwoord hangt ook af van wat jij zegt."
Als ze elkaar tegelijk proberen te antwoorden, ontstaat er een oneindige lus (een cirkel).

• A wacht op B.
• B wacht op A.
• Niemand zegt iets. Het systeem crasht.

In de echte wereld zie je dit bij elektrische circuits of software: als een uitgang direct terugkoppelt naar een ingang zonder vertraging, krijg je een "kortsluiting" of een oneindige lus.

3. De Oplossing: "Afhankelijke Bedrade Diagrammen"

De auteurs zeggen: "Oké, we kunnen deze snelle machines wel combineren, maar we moeten een nieuwe blauwdruk gebruiken om ze aan elkaar te koppelen."

Ze noemen dit Dependent Directed Wiring Diagrams (Afhankelijke Gerichte Bedrade Diagrammen).

De Analogie van de Stroomlijn:
Stel je voor dat je een fabriek ontwerpt. Je mag geen machines aan elkaar koppelen die in een cirkel draaien waar de producten nooit uitkomen.

• De oude blauwdrukken (voor Moore-machines) waren simpel: "Koppel uitgang A aan ingang B."
• De nieuwe blauwdrukken (voor Mealy-machines) zijn slimmer. Ze kijken niet alleen naar de draden, maar ook naar de afhankelijkheid.

Ze vragen: "Hangt het antwoord van Machine B echt direct af van het antwoord van Machine A?"

• Als ja: Dan mag je ze niet direct aan elkaar koppelen als dat een cirkel vormt.
• Als nee: Dan mag het wel.

Het paper introduceert een wiskundige tool (een "operad") die als een kwaliteitscontroleur fungeert. Deze tool kijkt naar je ontwerp en zegt: "Stop! Hier ontstaat een cirkel. Je kunt deze twee snelle machines niet zo koppelen." Of: "Goed, hier is geen cirkel, je mag ze koppelen."

4. Toepassing: Voorraad- en Stroomdiagrammen (Stock and Flow)

Het paper gebruikt deze theorie ook voor iets heel praktijks: Voorraad- en Stroomdiagrammen.
Dit zijn de diagrammen die je vaak ziet in milieustudies of economie.

• Voorraad (Stock): Een badkuip met water (bijvoorbeeld: de bevolking, of een voorraad geld).
• Stroom (Flow): De kraan die water toevoegt of het gat waar water uit loopt.

Vaak zijn deze diagrammen complex. De snelheid waarmee water uit de kraan loopt, hangt direct af van hoe vol het bad is, en dat hangt weer af van de temperatuur, die weer afhangt van de zon...

De auteurs tonen aan dat je deze complexe diagrammen nu veilig kunt combineren met hun nieuwe methode. Ze bewijzen dat als je twee van deze diagrammen aan elkaar koppelt (bijvoorbeeld een waterdiagram en een vervuilingsdiagram), je het resultaat kunt zien als één groot, werkend wiskundig model (een differentiaalvergelijking).

Samenvatting in één zin

Dit paper biedt een nieuwe, slimmere manier om complexe systemen (zoals snelle computers of milieumodellen) aan elkaar te koppelen, door een wiskundige "veiligheidscontrole" toe te voegen die voorkomt dat de systemen in een oneindige cirkel van verwarring terechtkomen.

Waarom is dit belangrijk?
Het stelt wetenschappers en ingenieurs in staat om grotere, complexere modellen te bouwen van de wereld om ons heen, zonder bang te hoeven zijn dat hun berekeningen vastlopen door logische cirkels. Het is alsof je een nieuwe set regels hebt voor het bouwen van legoblokken, zodat je nu ook de blokken kunt gebruiken die direct op elkaar reageren zonder dat het hele bouwwerk instort.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Dependent Directed Wiring Diagrams for Composing Instantaneous Systems" van Keri D'Angelo en Sophie Libkind, geschreven in het Nederlands.

Titel: Afhankelijke Gerichte Bedradingdiagrammen voor het Compositie van Instantane Systemen

1. Het Probleem

Traditionele methoden voor het compositie van systemen, zoals Moore-machines, veronderstellen dat de output volledig wordt afgeschermd van de input door een interne staat. Dit betekent dat de output op tijdstip $t$ alleen afhangt van de staat op tijdstip $t$, en niet direct van de input op datzelfde moment. Hierdoor kunnen Moore-machines veilig worden gecomposeerd via gerichte bedradingdiagrammen (Directed Wiring Diagrams - DWD), zelfs als er feedback-lussen (cycli) zijn tussen de componenten, omdat de staat de directe afhankelijkheid blokkeert.

Het probleem ontstaat bij Mealy-machines en andere systemen met instantane afhankelijkheid, waarbij de output direct en onmiddellijk wordt beïnvloed door de input (buiten de staat om). Wanneer men probeert Mealy-machines te compositeren met dezelfde bedradingpatronen als Moore-machines, kunnen er cycli van afhankelijkheid ontstaan. Bijvoorbeeld: de output van machine A is de input van machine B, en de output van B is direct de input van A. Dit leidt tot een logische paradox (een "cirkelredenering") waarbij de output niet kan worden berekend omdat deze afhankelijk is van zichzelf in dezelfde tijdsstap. Bestaande formalismen voor DWD kunnen deze instantane afhankelijkheden en de noodzaak van acycliciteit (afwezigheid van cycli) niet adequaat modelleren.

2. Methodologie

De auteurs introduceren een nieuw wiskundig raamwerk gebaseerd op Operad-theorie en Categorietheorie om dit probleem op te lossen. De aanpak bestaat uit de volgende stappen:

• Afhankelijkheidsrelaties: Ze definiëren afhankelijkheden tussen input- en outputpoorten als relaties (weergegeven als spans). Een output hangt af van een input als er een pad bestaat in het diagram.
• Dependent Directed Wiring Diagrams (dDWD): Ze bouwen een nieuwe categorie, genaamd dDWD, die voortkomt uit de categorie van gerichte bedradingdiagrammen (DWD).
  • Objecten in dDWD zijn interfaces die niet alleen input- en outputpoorten specificeren, maar ook een afhankelijkheidsrelatie tussen deze poorten bijhouden.
  • Morfismen in dDWD zijn bedradingdiagrammen die acyclisch moeten zijn. Dit betekent dat wanneer je de trace-wires (verbindingen tussen systemen) combineert met de interne afhankelijkheidsrelaties van de systemen, er geen cycli mogen ontstaan.
• Algebra's voor Compositie: Ze definiëren twee algebra's over de operad van dDWD:
  1. Mealy-algebra: Een algebra die Mealy-machines compositieert volgens de regels van dDWD. De compositie wordt berekend door het vinden van een uniek vast punt (fixed point) van een endomorfisme dat de signaalstroom door de acyclische graaf beschrijft.
  2. Stock-and-Flow-algebra (SF): Een algebra voor het compositie van voorraad-en-stroomdiagrammen (stock-and-flow diagrams), waarbij hulpvariabelen (auxiliary variables) direct afhankelijk kunnen zijn van inputs en andere variabelen.
• Semantische Koppeling: Ze bewijzen dat er een monoidale natuurlijke transformatie bestaat van de Stock-and-Flow algebra naar de Mealy-algebra. Dit betekent dat elk stock-and-flow diagram kan worden geïnterpreteerd als een Mealy-machine (en dus als een differentiaalvergelijking) die de compositie-regels respecteert.

3. Belangrijkste Bijdragen

• Operad van Afhankelijke Gerichte Bedradingdiagrammen (dDWD): De introductie van een operad die expliciet afhankelijkheden tussen input en output bijhoudt en compositie alleen toestaat als deze afhankelijkheden geen cycli creëren. Dit lost het probleem van instantane feedback op.
• Formalisatie van Mealy-machines Compositie: Een rigoureuze definitie van hoe Mealy-machines kunnen worden samengesteld zonder onberekenbare cycli, met behulp van de theorie van vaste punten op acyclische grafen.
• Uitbreiding van Stock-and-Flow Diagrammen: Een nieuwe definitie van open stock-and-flow diagrammen die exogene variabelen, links tussen hulpvariabelen en directe output-afhankelijkheden omvat.
• Semantische Consistentie: Het bewijs dat de interpretatie van stock-and-flow diagrammen als differentiaalvergelijkingen (via Mealy-machines) compatibel is met de compositie-operaties. Dit verbindt grafische modellering direct met dynamische systemen.
• Software-implementatie: De auteurs verwijzen naar de implementatie van deze theorie in het Julia-pakket AlgebraicDynamics.jl.

4. Resultaten

• Correctheid van Compositie: Het artikel toont aan dat door de beperking tot acyclische afhankelijke diagrammen, de output van gecomposeerde instantane systemen altijd goed gedefinieerd en berekenbaar is.
• Vaste Punten: Voor elke acyclische configuratie bestaat er een unieke oplossing (vast punt) voor de signaalwaarden, wat de berekenbaarheid garandeert.
• Voorbeeldtoepassingen:
  • Het succesvol compositie van Mealy-machines die de Fibonacci-reeks berekenen (waarbij output direct input beïnvloedt).
  • Het modelleren van complexe systemen zoals het SIR-epidemiologische model en systemen met water- en vervuilingsvoorraden, waarbij de stromen direct afhankelijk zijn van de huidige staat en externe inputs.
• Natuurlijke Transformatie: Het bewijs dat de transformatie van diagram naar differentiaalvergelijking een monoidale natuurlijke transformatie is, bevestigt dat de compositie van modellen leidt tot de compositie van de onderliggende dynamica.

5. Betekenis en Impact

Dit werk is significant voor het veld van compositional engineering en systeemtheorie om de volgende redenen:

1. Brug tussen Discrete en Continue Systemen: Het biedt een uniform raamwerk om zowel discrete automata (Mealy-machines) als continue systemen (differentiaalvergelijkingen via stock-and-flow) op dezelfde manier te compositeren.
2. Veiligheid bij Instantane Feedback: Het lost een fundamenteel probleem op in het modelleren van systemen met directe feedback (zoals elektronische schakelingen of real-time regelsystemen) door een formele manier te bieden om cycli te detecteren en te voorkomen die zouden leiden tot onberekenbaarheid.
3. Modulariteit: Het stelt onderzoekers en ingenieurs in staat om complexe systemen op te bouwen uit kleinere, onafhankelijke componenten, waarbij de afhankelijkheden tussen componenten expliciet worden getraceerd en geverifieerd.
4. Toekomstige Toepassingen: De methode opent de deur voor geavanceerde softwaretools (zoals AlgebraicJulia) die automatisch kunnen controleren of een systeemontwerp geldig is voordat het wordt gesimuleerd, en voor het ontwikkelen van dubbel-categorische systeemtheorieën.

Kortom, de auteurs hebben een wiskundig robuust formalisme ontwikkeld dat het mogelijk maakt om complexe, interactieve systemen met instantane afhankelijkheden veilig en modulair te bouwen en te analyseren.