What does it mean for a system to compute?

Dit artikel presenteert een breed toepasbaar raamwerk om te bepalen welke berekeningen door dynamische systemen, zowel natuurlijk als kunstmatig, worden uitgevoerd door de evolutie van het systeem te koppelen aan die van een abstracte rekenmachine.

De kern

Wat betekent het voor een systeem om te "rekenen"?
Een samenvatting van het onderzoek van Wolpert en Korbel in begrijpelijk Nederlands.

Stel je voor dat je naar een rivier kijkt die over stenen stroomt, of naar een zwerm vogels die door de lucht cirkelt. Zien we daar alleen natuur? Of zien we daar een computer die aan het werk is?

Dit is de grote vraag die David Wolpert en Jan Korbel in hun paper proberen te beantwoorden. Ze onderscheiden twee soorten "computers": die door mensen zijn gebouwd en die die we in de natuur aantreffen.

1. De twee soorten computers: De Bouwer en de Ontdekker

De Gebouwde Computer (De Bouwer)
Denk aan je laptop of smartphone. Deze zijn door mensen ontworpen. De ingenieur die de chip heeft gemaakt, heeft precies bepaald: "Als deze draad stroom krijgt, betekent dit een '1'. Als die andere draad stroom krijgt, betekent dit een '0'."

• De sleutel: We hebben de "decoderingscode" (de vertaalsleutel) al voordat het systeem aan gaat. We weten precies wat de fysieke onderdelen betekenen in termen van logica. Het is als een boek dat je schrijft: je weet precies wat elk woord betekent.

De Niet-Gebouwde Computer (De Ontdekker)
Nu kijk je naar een menselijk brein, een mierennest, of een wervelende storm. Niemand heeft deze systemen ontworpen om te rekenen. Toch denken we vaak dat ze "rekenen" (bijvoorbeeld: een mier die een route zoekt, of een hersencel die een signaal verwerkt).

• Het probleem: Er is geen handleiding. Er is geen ingenieur die zegt: "Deze zenuwcel is de 'plus'-knop."
• De uitdaging: Als we naar een storm kijken, kunnen we oneindig veel manieren bedenken om de beweging van de luchtdeeltjes te vertalen naar een rekenmachine. Misschien is de wind een optelmachine, of misschien is het een zoekmachine. Hoe weten we welke "rekening" het systeem eigenlijk uitvoert?

2. De Grote Uitdaging: De Vertaalsleutel vinden

De auteurs zeggen: "Elk dynamisch systeem kan theoretisch gezien als een computer worden gezien, afhankelijk van hoe je de code kraken."

Stel je voor dat je een oude, mysterieuze machine vindt in een grot. Je ziet tandwielen die draaien.

• Als je zegt: "Tandwiel A is een 'ja', Tandwiel B is een 'nee'", dan lijkt het een rekenmachine voor ja/nee-vragen.
• Als je zegt: "Tandwiel A is een 'rood', Tandwiel B is een 'blauw'", dan lijkt het een machine die kleuren mengt.

De vraag is: Hoe weten we welke vertaalsleutel de 'echte' is?

De paper stelt een nieuw raamwerk voor. Ze zeggen: we moeten kijken naar de beweging van het systeem.

• Als het systeem beweegt van toestand A naar toestand B, moet die beweging overeenkomen met een logische stap in een abstracte computer (zoals een Turing-machine).
• Het is alsof je kijkt naar een danser. Als de danser van positie 1 naar 2 springt, moet die sprong overeenkomen met een stap in een algoritme. Als de danser willekeurig springt, is het geen berekening. Als de sprongen een patroon volgen dat precies past bij een wiskundige formule, dan "rekenen" ze.

3. Waarom is dit belangrijk? (De "Waarde" van het rekenen)

Soms is het niet belangrijk om te weten wat er precies wordt berekend, maar hoe goed het systeem het doet.

Stel je een vogel voor die vliegt.

• De berekening: De vogel berekent continu de windrichting en de positie van zijn nest.
• De waarde: Het doel is niet de berekening zelf, maar het overleven. Als de vogel de berekening goed doet, eet hij genoeg en overleeft hij. Als hij het fout doet, sterft hij.

De auteurs stellen dat we voor natuurlijke systemen (zoals organismen) moeten kijken naar de waarde van de berekening. Hoeveel helpt deze berekening het systeem om te overleven of energie te winnen? Het is alsof je een speler in een computerspel beoordeelt: het maakt niet uit welke knoppen hij precies indrukt, maar of hij het spel wint.

4. Voorbeelden uit de natuur

De paper bespreekt verschillende voorbeelden van systemen die we als computers zien:

• Hersenen: Ze rekenen informatie om in gedachten en acties.
• Mierenkolonies: Samen vinden ze de kortste weg naar voedsel (een soort optimalisatie-algoritme).
• Chemische reacties: In een cel kunnen moleculen met elkaar reageren alsof ze een logische schakeling zijn (zoals een computerchip, maar dan gemaakt van soep).
• Stromend water: Zelfs een rivier kan, in theorie, zo complex stromen dat het wiskundige problemen oplost (hoewel dit lastig is om te bewijzen).

5. De Toekomst: Wat kunnen we nog leren?

De auteurs sluiten af met een aantal spannende vragen voor de toekomst:

• Hoe meten we hoeveel er wordt berekend? Kunnen we zeggen dat een menselijk brein "meer" rekent dan een mierennest? Misschien kunnen we kijken naar hoe complex de patronen zijn.
• Open systemen: Een echte computer in de natuur (zoals een dier) is nooit gesloten. Het krijgt continu nieuwe input van de wereld. Hoe rekenen we daarvoor?
• Collectief rekenen: Als we een zwerm vogels bekijken, rekenen ze dan samen als één groot brein, of is het gewoon een hoop individuen?

Conclusie in één zin

Deze paper probeert een algemene taal te vinden om te zeggen: "Dit natuurlijke systeem (zoals een storm of een cel) is een computer, en dit is hoe we de beweging ervan vertalen naar logica, zonder dat er een menselijke ingenieur is die de handleiding heeft geschreven."

Het is een zoektocht naar de code van de natuur, om te begrijpen hoe het universum zelf "rekenen" gebruikt om complexe dingen te doen.

Technische samenvatting

Probleemstelling

Het artikel adresseert een fundamenteel probleem in de complexiteitswetenschap en de theoretische informatica: hoe definieert men formeel wat het betekent dat een dynamisch systeem "berekent" (computes), vooral wanneer dat systeem niet door mensen is ontworpen voor dat doel?

• Gestructureerde vs. Niet-gestructureerde Computers: Voor door mensen gebouwde computers (zoals digitale computers) is de relatie tussen de fysieke toestand van het systeem en de logische variabelen van de berekening expliciet bekend en vooraf bepaald (de "decoding map"). Bij natuurlijk voorkomende dynamische systemen (zoals het menselijk brein, cellulaire netwerken, turbulentie of insectenkoloniën) ontbreekt deze vooraf gedefinieerde mapping.
• Het Decodatie-probleem: Zonder een vooraf vastgestelde decodatie kan bijna elk dynamisch systeem worden geïnterpreteerd als het uitvoeren van oneindig veel verschillende berekeningen, afhankelijk van hoe men de fysieke variabelen koppelt aan logische variabelen. De kernvraag is: bestaat er een principiële manier om te bepalen welke berekening (of welke set berekeningen) een gegeven dynamisch systeem daadwerkelijk uitvoert, zonder een vooraf gedefinieerde mapping?

Methodologie

De auteurs introduceren een breed toepasbaar wiskundig raamwerk om dit probleem aan te pakken. De methodologie bestaat uit de volgende stappen:

1. Formele Definitie van Dynamische Systemen:
   Een dynamisch systeem wordt gedefinieerd als een drietal $(X, T, f)$, waarbij $X$ de toestandsruimte is, $T$ de tijd, en $f$ de evolutie-operator die de toestand op tijdstip $t$ naar $t'$ evolueert.

2. Definitie van "Emulatie" (Nabootsing):
   De auteurs definiëren wanneer een dynamisch systeem $A$ (met toestandsruimte $X$) een computationeel machine $B$ (met toestandsruimte $Y$) emuleert. Dit gebeurt via een coarse-graining (grofkorrelige mapping).

   • Er bestaat een verzameling-functie $\phi$ die elementen uit $Y$ mapt naar niet-overlappende deelverzamelingen van $X$.
   • De dynamica van $X$ emuleert die van $Y$ als voor elke toestand $y \in Y$ en tijdstippen $t, t'$ geldt dat de evolutie van de verzameling $\phi(y)$ binnen $X$ resulteert in een toestand die binnen $\phi(g(t, t', y))$ valt, waarbij $g$ de dynamica van de computationele machine is.
   • Formeel: $f(t, t', \phi(y)) \subseteq \phi(g(t, t', y))$.
   • De inverse functie $\phi^{-1}$ fungeert als de decoding-functie (van fysieke toestand naar logische variabele), en $\phi$ als de encoding-functie.

3. Beperkingen en Complexiteit:
   Om te voorkomen dat de berekening "verborgen" zit in de mapping zelf (bijvoorbeeld dat de decoding-functie al de oplossing berekent), stellen de auteurs beperkingen op de computationele complexiteit van de mapping-functies ($\phi$ en $\phi^{-1}$). Deze moeten bijvoorbeeld polynomiaal tijd- en ruimte-efficiënt zijn, zodat de daadwerkelijke dynamica van het systeem de berekening uitvoert en niet de interpretatie ervan.

4. Analyse van Bestaande Voorbeelden:
   Het raamwerk wordt toegepast op diverse systemen uit de literatuur, waaronder:

   • Neuroscience en biologische systemen: Breinen, cellulaire netwerken, en zwermen.
   • Cellulaire automata (CA): Waar de initiële configuratie als input dient, maar de mapping niet vooraf bekend is.
   • Chemische reactienetwerken (CRN): Waar concentraties logische toestanden vertegenwoordigen.
   • Vloeistofcomputers (Fluid computers): Systemen die gebaseerd zijn op de Navier-Stokes of Euler-vergelijkingen.

Belangrijkste Bijdragen en Resultaten

• Unificerend Raamwerk: Het artikel biedt de eerste algemene, formele definitie van "emulatie" die toepasbaar is op zowel door mensen gebouwde als natuurlijk voorkomende systemen. Het lost het probleem op van het identificeren van berekeningen zonder voorafgaande kennis van de decoding.
• Onderscheid tussen Emulatie en "Turing-volledigheid":
  De auteurs maken een cruciaal onderscheid tussen systemen die een Turing-machine (TM) emuleren volgens hun definitie, en systemen die "Turing-volledig" zijn in de zin van recente studies over vloeistofstromen (zoals Tao en collega's).
  • Resultaat: Veel systemen die in de literatuur als "Turing-volledig" worden bestempeld (zoals bepaalde vloeistofstromen), voldoen niet aan de strikte definitie van emulatie van de auteurs. Deze systemen kunnen wel beslissen of een machine stopt (halting problem), maar ze emuleren niet de volledige stap-voor-stap dynamica van de TM, noch bieden ze een directe mapping van de interne toestanden. Ze implementeren slechts een partiële functie zonder de volledige evolutie van de toestandsruimte te kopiëren.
• Niet-berekenbaarheid (Uncomputability):
  Het artikel bespreekt dat er dynamische systemen bestaan waarvan bepaalde eigenschappen onberekenbaar zijn (bijvoorbeeld het bepalen van het fase-diagram van een kwantum-systeem of de locatie van een fase-overgang gebaseerd op Chaitin's constante). Dit suggereert dat fysieke systemen potentieel "super-Turing" vermogen kunnen hebben, hoewel dit de geldigheid van de Church-Turing stelling in fysieke contexten uitdaagt.
• Waarde van Berekening:
  In plaats van alleen te focussen op wat er wordt berekend, introduceren de auteurs het concept van de "waarde van berekening" (value of computation). Voor biologische systemen wordt de waarde gedefinieerd in termen van "levensvatbaarheid" (viability), zoals het vermogen om vrije energie te extraheren of zich aan te passen aan omgevingsveranderingen. De kwaliteit van de berekening wordt gemeten aan de hand van hoe goed het systeem zijn doelen bereikt.

Significantie en Toekomstperspectief

• Fundamentele Theorie: Het werk legt een brug tussen de theoretische informatica (Turing-machines, complexiteitstheorie) en de natuurwetenschappen (thermodynamica, biologie, dynamische systemen). Het biedt een taal om te spreken over "computing" in het universum zonder antropocentrische vooroordelen.
• Biologische Inzicht: Het raamwerk helpt bij het begrijpen van hoe biologische systemen (van cellen tot koloniën) informatie verwerken en beslissingen nemen, zonder dat we hoeven aan te nemen dat ze zijn ontworpen als computers.
• Toekomstig Onderzoek: De auteurs identificeren belangrijke open vragen, waaronder:
  • Hoe om te gaan met systemen die continu input en output verwerken (continual computers) in plaats van eenmalige berekeningen.
  • Het kwantificeren van de hoeveelheid berekening (via Kolmogorov-complexiteit of Markov-ketens) in plaats van de exacte aard van de berekening.
  • Het analyseren van collectieve berekening in gedistribueerde systemen.
  • De rol van input- en outputsystemen in het definiëren van een bruikbare computer in de echte wereld.

Kortom, dit artikel stelt een rigoureuze, maar flexibele definitie voor van computation in dynamische systemen, waardoor het mogelijk wordt om de computationele capaciteiten van de natuur (en kunstmatige systemen) objectief te analyseren en te vergelijken, los van menselijke interpretatie.