Maths 'Game of Life' afslører længe søgte gentagne mønstre | Quanta Magasinet

I 1969 udtænkte den britiske matematiker John Conway et forbløffende simpelt sæt regler til at skabe kompleks adfærd. Hans Game of Life, ofte blot omtalt som Life, udfolder sig på et uendeligt firkantet gitter af celler. Hver celle kan enten være "levende" eller "død". Gitteret udvikler sig over en række drejninger (eller "generationer"), hvor hver celles skæbne bestemmes af de otte celler, der omgiver den. Reglerne er som følger:

1. Fødsel: En død celle med præcis tre levende naboer bliver levende.
2. Overlevelse: En levende celle med to eller tre levende naboer forbliver i live.
3. Død: En levende celle med færre end to eller mere end tre levende naboer dør.

Disse enkle regler skaber en forbløffende mangfoldig række af mønstre eller "livsformer", der udvikler sig fra de mange forskellige mulige startkonfigurationer af gitteret. Elskere af spillet har talt og taxonomiseret disse mønstre i en stadigt voksende online katalog. Conway opdagede et mønster kaldet blinker, som svinger mellem to tilstande.

Det næste år fandt han et meget mere kompliceret mønster kaldet pulsaren, som svinger mellem tre forskellige tilstande.

Kort efter at oscillatorer blev opdaget, spekulerede spillets tidlige opdagelsesrejsende på, om der findes oscillatorer fra hver periode. "Først så vi kun periode 1, 2, 3, 4 og 15," sagde computerprogrammøren og matematikeren Bill Gosper, som ville fortsætte med at opdage 17 forskellige nye oscillatorer i løbet af de næste årtier. Periode 15-oscillatorer (vist nedenfor) dukkede overraskende ofte op i tilfældige søgninger.

Overraskelser lurede for dem, der var villige til at finde dem. "Fra timer og dage med visning virkede periode 5 umulig," sagde Gosper. Så i 1971, to år efter at spillet blev opfundet, blev der fundet et. Jagten på nye oscillatorer voksede til et hovedfokus i spillet, en søgen, der blev styrket af computerteknologiens fremkomst. Beretninger om hemmelige søgninger udført på kontorcomputere er blevet en hjørnesten i spillets folklore. "Mængden af ​​computertid stjålet fra virksomheders og universitets mainframes var svimlende," sagde Gosper.

Igennem 1970'erne fyldte matematikere og hobbyfolk de andre korte perioder ud og fandt en snert af længere perioder. Til sidst opdagede matematikere en systematisk måde at bygge langtidsoscillatorer på. Men oscillatorer med perioder mellem 15 og 43 viste sig at være svære at finde. "Folk har forsøgt at finde ud af midten i årevis," sagde Maia Karpovich, en kandidatstuderende ved University of Maryland. At udfylde hullerne tvang forskerne til at opfinde en række nye teknikker, der rykkede grænserne for, hvad man troede var muligt med cellulære automater, som matematikere kalder udviklende net som Life.

Nu har Karpovich og seks medforfattere annonceret i en december fortryk at de har fundet de sidste to manglende perioder: 19 og 41. Med disse huller udfyldt er livet nu kendt for at være "omniperiodisk" - navngiv et positivt heltal, og der eksisterer et mønster, der gentager sig selv efter så mange trin.

Det spirende samfund, der er viet til at studere livet, som omfatter mange forskningsmatematikere, men også mange hobbyfolk, har ikke kun fundet oscillatorer, men alle slags nye mønstre. De har fundet mønstre, der rejser på tværs af gitteret, døbt rumskibe og mønstre, der bygger andre mønstre: våben, konstruktører og opdrættere. De fandt mønstre, der beregner primtal, og endda mønstre, der kan udføre vilkårligt komplicerede algoritmer.

Oscillatorer med perioder kortere end 15 kan findes manuelt eller med rudimentære algoritmer, der søger efter oscillatorer en celle ad gangen. Men efterhånden som perioden bliver større, øges kompleksiteten også, hvilket gør brute-force-søgninger langt mindre effektive. "I små perioder kan du søge direkte," sagde Matthias Merzenich, en medforfatter af det nye papir, der opdagede den første periode-31 oscillator i 2010. "Men du kan ikke rigtig gå ud over det. Du kan ikke bare vælge en periode og søge efter den." (Merzenich fik sin doktorgrad i matematik fra Oregon State University i 2021, men arbejder i øjeblikket på en gård.)

I 1996 viste David Buckingham, en canadisk freelance computerkonsulent og livsentusiast, der havde søgt efter mønstre siden slutningen af ​​1970'erne, at det var muligt at konstruere oscillatorer fra periode 61 og højere ved at sende et mønster rundt i et lukket spor i en endeløs sløjfe . Ved at kontrollere længden af ​​løkken - og den tid, det tog mønsteret at gennemføre en rundtur - fandt Buckingham ud af, at han kunne gøre perioden så stor, som han havde lyst. "Det er kemi uden de sjove lugte eller ødelagte glasvarer," sagde han. "Som at bygge forbindelser og derefter udforske interaktionerne mellem dem." Det betød, at han i ét hug havde fundet på en måde at konstruere oscillatorer med vilkårligt lange perioder, så længe de var længere end 61.

Der var et væld af resultater i midten af ​​1990'erne, hvor mange af de manglende oscillatorer mellem 15 og 61 blev opdaget gennem kreative kombinationer af kendte oscillatorer, som havde fået en række farverige navne. Cateringfirmaer blev kombineret med trafiklys, vulkaner spyttede gnister ud, og spisende spiste svævefly.

Ved begyndelsen af ​​det 21. århundrede var der stadig kun et dusin perioder udestående. "Det virkede meget muligt at løse dette problem," sagde Merzenich. I 2013 forbedrede en ny opdagelse kaldet Snark-løkken Buckinghams 1996-teknik og sænkede cutoff-grænsen, over hvilken det var let at konstruere oscillatorer fra 61 til 43. Dette efterlod kun fem manglende perioder. En mere blev opdaget i 2019, og to mere i 2022, hvilket efterlod kun 19 og 41 - begge prime. "Prime er sværere, fordi du ikke kan bruge små periodiske oscillatorer til at konstruere dem," sagde Merzenich.

Mitchell Riley, en postdoc-forsker ved New York University Abu Dhabi og en anden medforfatter af det nye papir, har længe været fascineret af en type oscillator kaldet en hassler. "Måden Hasslers arbejder på er, at du har et aktivt mønster i midten og nogle stabile ting på ydersiden, der reagerer med det," forklarede Riley. De stabile ting, kaldet en katalysator, er der for at skubbe det aktive mønster tilbage til dets oprindelige tilstand.

Det er svært at designe dem. "Alle disse mønstre er utrolig skrøbelige," sagde Riley. "Hvis du sætter en enkelt prik ud af stedet, eksploderer de som regel bare."

Riley skabte et program kaldet Barrister for at lede efter nye katalysatorer. »Det, vi leder efter, er stilleben, der er robuste. Hele pointen er, at vi vil have dem til at interagere med, hvad der sker i midten og derefter komme sig, sagde Riley.

Riley fodrede katalysatorer, som Barrister fandt, i et andet søgeprogram, der parrede dem med aktive mønstre. Dette førte for det meste til fiaskoer, sagde han. "Det er ret sjældent, at en af ​​disse katalysatorer overlever interaktionen. Der er ingen garanti for succes. Du krydser bare fingre og håber, at du rammer jackpotten. Det føles lidt som gambling.”

Til sidst gav hans indsats pote. Efter et par næsten uheld - og en ændring af koden, der udvidede søgningen til at omfatte symmetriske mønstre - fandt han en katalysatorinteraktion, der kunne opretholde en periode-19-oscillator. "Folk havde prøvet alle slags virkelig komplicerede søgninger med masser af katalysatorer og masser af sjældne aktive ting i midten, men alt, hvad der var nødvendigt, var at finde denne nye chunky katalysator," sagde Riley.

Den sidste manglende periode, 41, blev fundet af Nicolo Brown, en anden medforfatter, som stadig er en bachelor i matematik ved University of California, Santa Cruz. Brown brugte svævefly som katalysatorer, en idé først foreslået af Merzenich.

"Vi har opdaget så meget dyb adfærd i løbet af de sidste 10 år," sagde Karpovich. "Alle fejrer i en uge - og går så videre til andre ting. Der er så mange andre problemer at løse." Kan oscillatorer i en given periode gøres mindre? Kan der findes oscillatorer, hvor hver enkelt celle svinger? Kan våben fremstilles med bestemte perioder? Kan rumskibe fåes til at rejse med særlige hastigheder?

Som Buckingham udtrykte det: "Det er som at være barn i en uendelig legetøjsbutik."