Math’s ‘Game of Life’ onthult lang gezochte herhalende patronen | Quanta-tijdschrift

In 1969 bedacht de Britse wiskundige John Conway een verleidelijk eenvoudige reeks regels voor het creëren van complex gedrag. Zijn Game of Life, vaak eenvoudigweg Life genoemd, ontvouwt zich in een oneindig vierkant raster van cellen. Elke cel kan ‘levend’ of ‘dood’ zijn. Het raster evolueert over een reeks beurten (of ‘generaties’), waarbij het lot van elke cel wordt bepaald door de acht cellen eromheen. De regels zijn als volgt:

1. Geboorte: Een dode cel met precies drie levende buren wordt levend.
2. Overleving: Een levende cel met twee of drie levende buren blijft in leven.
3. Dood: Een levende cel met minder dan twee of meer dan drie levende buren sterft.

Deze eenvoudige regels creëren een verbazingwekkend diverse reeks patronen, of ‘levensvormen’, die evolueren uit de vele verschillende mogelijke startconfiguraties van het raster. Liefhebbers van het spel hebben deze patronen in een steeds groter wordende vorm opgeteld en getaxonomiseerd online catalogus. Conway ontdekte een patroon dat de blinker wordt genoemd en dat tussen twee toestanden oscilleert.

Het jaar daarop ontdekte hij een veel gecompliceerder patroon, de pulsar genaamd, die tussen drie verschillende toestanden oscilleert.

Kort nadat oscillatoren waren ontdekt, vroegen de vroege onderzoekers van het spel zich af of er oscillatoren uit elke periode bestaan. “In eerste instantie zagen we alleen de perioden 1, 2, 3, 4 en 15”, zegt computerprogrammeur en wiskundige Bill Gosper, die in de daaropvolgende decennia zeventien verschillende nieuwe oscillatoren zou ontdekken. Oscillatoren uit periode 17 (hieronder weergegeven) kwamen verrassend vaak naar voren in willekeurige zoekopdrachten.

Er lagen verrassingen op de loer voor degenen die ze wilden vinden. “Na uren en dagen kijken leek periode 5 onmogelijk”, zei Gosper. In 1971, twee jaar nadat het spel was uitgevonden, werd er één gevonden. De jacht op nieuwe oscillatoren groeide uit tot een belangrijk aandachtspunt van het spel, een zoektocht die werd versterkt door de komst van computertechnologie. Verslagen van geheime zoekopdrachten op kantoorcomputers zijn een hoeksteen van de folklore van het spel geworden. “De hoeveelheid computertijd die werd gestolen van mainframes van bedrijven en universiteiten was enorm”, zegt Gosper.

Gedurende de jaren zeventig vulden wiskundigen en hobbyisten de andere korte perioden in en vonden een paar langere perioden. Uiteindelijk ontdekten wiskundigen een systematische manier om oscillatoren met een lange periode te bouwen. Maar oscillatoren met perioden tussen 1970 en 15 bleken moeilijk te vinden. “Mensen proberen al jaren het midden te vinden”, zegt hij Maia Karpovich, een afgestudeerde student aan de Universiteit van Maryland. Het opvullen van de gaten dwong onderzoekers een hele reeks nieuwe technieken te bedenken die de grenzen verlegden van wat voor mogelijk werd gehouden met cellulaire automaten, zoals wiskundigen evoluerende rasters zoals het leven noemen.

Nu hebben Karpovich en zes co-auteurs dit aangekondigd in een voordruk december dat ze de laatste twee ontbrekende perioden hebben gevonden: 19 en 41. Nu deze gaten zijn opgevuld, is het leven nu bekend als ‘omniperiodisch’ – noem een ​​positief geheel getal, en er bestaat een patroon dat zichzelf na zoveel stappen herhaalt.

De snelgroeiende gemeenschap die zich toelegt op het bestuderen van het leven, waartoe veel onderzoekswiskundigen maar ook veel hobbyisten behoren, heeft niet alleen oscillatoren gevonden, maar ook allerlei nieuwe patronen. Ze hebben patronen gevonden die door het raster reizen, ruimteschepen genoemd, en patronen die andere patronen bouwen: wapens, constructeurs en fokkers. Ze vonden patronen die priemgetallen berekenen, en zelfs patronen die willekeurig ingewikkelde algoritmen kunnen uitvoeren.

Oscillatoren met perioden korter dan 15 kunnen handmatig worden gevonden of met rudimentaire algoritmen die cel voor cel naar oscillatoren zoeken. Maar naarmate de periode groter wordt, neemt ook de complexiteit toe, waardoor zoekopdrachten met brute kracht veel minder effectief worden. “Voor korte periodes kun je direct zoeken”, zegt Matthias Merzenich, co-auteur van het nieuwe artikel dat in 31 de eerste periode-2010-oscillator ontdekte. “Maar verder dan dat kun je niet echt gaan. Je kunt niet zomaar een periode kiezen en daarnaar zoeken.” (Merzenich behaalde zijn doctoraat in wiskunde aan de Oregon State University in 2021, maar werkt momenteel op een boerderij.)

In 1996 toonde David Buckingham, een Canadese freelance computerconsulent en levensliefhebber die sinds eind jaren zeventig naar patronen zocht, aan dat het mogelijk was oscillatoren uit periode 1970 en hoger te construeren door een patroon in een eindeloze lus rond een gesloten spoor te sturen. . Door de lengte van de lus te beheersen – en de tijd die het patroon nodig had om één rondreis te voltooien – ontdekte Buckingham dat hij de periode zo groot kon maken als hij wilde. “Het is chemie zonder de vreemde geuren of gebroken glaswerk”, zei hij. “Zoals het bouwen van verbindingen en het onderzoeken van de interacties daartussen.” Dit betekende dat hij in één klap een manier had bedacht om oscillatoren met willekeurig lange perioden te construeren, zolang ze maar langer waren dan 61.

Er was een hele reeks resultaten halverwege de jaren negentig, toen veel van de ontbrekende oscillatoren tussen 1990 en 15 werden ontdekt door creatieve combinaties van bekende oscillatoren, die een hele reeks kleurrijke namen hadden gekregen. Traiteurs werden gecombineerd met verkeerslichten, vulkanen spuwden vonken uit en eters aten zweefvliegtuigen.

Aan het begin van de 21e eeuw waren er nog maar een tiental periodes uitstaande. “Het leek heel goed mogelijk om dit probleem op te lossen”, zei Merzenich. In 2013 verbeterde een nieuwe ontdekking, de Snark-lus, de techniek van Buckingham uit 1996 en verlaagde de grens waarboven het gemakkelijk was om oscillatoren te construeren van 61 naar 43. Hierdoor bleven er slechts vijf ontbrekende perioden over. Er werd er nog één ontdekt in 2019, en nog twee in 2022, waardoor er slechts 19 en 41 overbleven – beide prime. “Priemgetallen zijn moeilijker omdat je geen oscillatoren met een kleine periode kunt gebruiken om ze te construeren,” zei Merzenich.

Mitchell Riley, een postdoctoraal onderzoeker aan de New York University Abu Dhabi en een andere co-auteur van het nieuwe artikel, is al lang geïntrigeerd door een soort oscillator die een hustler wordt genoemd. “De manier waarop gedoe werkt, is dat je een actief patroon in het midden hebt en een aantal stabiele dingen aan de buitenkant die daarmee reageren,” legde Riley uit. Het stabiele spul, een katalysator genoemd, is er om het actieve patroon terug in zijn oorspronkelijke staat te brengen.

Het ontwerpen ervan is moeilijk. “Al deze patronen zijn ongelooflijk kwetsbaar”, zegt Riley. “Als je ook maar één punt op zijn plaats zet, ontploffen ze meestal.”

Riley creëerde een programma genaamd Barrister om naar nieuwe katalysatoren te zoeken. “Wat we zoeken zijn stillevens die robuust zijn. Het hele punt is dat we willen dat ze interactie hebben met wat er in het midden gebeurt en dan herstellen, ‘zei Riley.

Riley voerde katalysatoren die Barrister vond in een ander zoekprogramma dat ze koppelde aan actieve patronen. Dit leidde vooral tot mislukkingen, zei hij. “Het komt vrij zelden voor dat een van deze katalysatoren de interactie overleeft. Er is geen garantie op succes. Je kruist gewoon je vingers en hoopt dat je de jackpot wint. Het voelt een beetje als gokken.”

Uiteindelijk werd zijn weddenschap beloond. Na een paar bijna-ongelukken – en een aanpassing aan de code die de zoektocht uitbreidde naar symmetrische patronen – vond hij een katalysatorinteractie die een periode-19-oscillator kon ondersteunen. "Mensen hadden allerlei ingewikkelde zoekopdrachten geprobeerd met veel katalysatoren en veel zeldzame actieve dingen in het midden, maar het enige dat nodig was, was het vinden van deze nieuwe, stevige katalysator", zei Riley.

De laatste ontbrekende periode, 41, werd gevonden door Nicolo Brown, een andere co-auteur, die nog steeds wiskunde studeert aan de Universiteit van Californië, Santa Cruz. Brown gebruikte zweefvliegtuigen als katalysator, een idee dat voor het eerst door Merzenich werd voorgesteld.

“We hebben de afgelopen tien jaar zoveel diepgaand gedrag ontdekt”, zei Karpovich. “Iedereen viert een week lang feest – en gaat dan verder met andere dingen. Er zijn nog zoveel andere problemen die opgelost moeten worden.” Kunnen oscillatoren van een bepaalde periode kleiner worden gemaakt? Zijn er oscillatoren te vinden waarin elke afzonderlijke cel oscilleert? Kunnen wapens met bepaalde perioden worden gemaakt? Kunnen ruimteschepen met bepaalde snelheden reizen?

Zoals Buckingham het verwoordde: ‘Het is alsof je een kind bent in een oneindige speelgoedwinkel.’