Maths "Game of Life" avslører lenge søkte gjentakende mønstre | Quanta Magazine

I 1969 utviklet den britiske matematikeren John Conway et forlokkende enkelt sett med regler for å skape kompleks atferd. Hans Game of Life, ofte referert til som Life, utspiller seg på et uendelig firkantet rutenett av celler. Hver celle kan enten være "levende" eller "død". Rutenettet utvikler seg over en serie svinger (eller "generasjoner"), med skjebnen til hver celle bestemt av de åtte cellene som omgir den. Reglene er som følger:

1. Fødsel: En død celle med nøyaktig tre levende naboer blir levende.
2. Overlevelse: En levende celle med to eller tre levende naboer holder seg i live.
3. Død: En levende celle med færre enn to eller flere enn tre levende naboer dør.

Disse enkle reglene skaper en forbløffende mangfoldig rekke mønstre, eller "livsformer", som utvikler seg fra de mange forskjellige mulige startkonfigurasjonene til rutenettet. Elskere av spillet har samlet og taksonomisert disse mønstrene i en stadig voksende online katalog. Conway oppdaget et mønster kalt blinker, som svinger mellom to tilstander.

Det neste året fant han et mye mer komplisert mønster kalt pulsaren, som svinger mellom tre forskjellige tilstander.

Rett etter at oscillatorer ble oppdaget, lurte de tidlige oppdagere av spillet på om det finnes oscillatorer fra hver periode. "Til å begynne med så vi bare periode 1, 2, 3, 4 og 15," sa dataprogrammereren og matematikeren Bill Gosper, som skulle fortsette å oppdage 17 forskjellige nye oscillatorer i løpet av de neste tiårene. Periode 15-oscillatorer (vist nedenfor) dukket opp overraskende ofte i tilfeldige søk.

Overraskelser lurte for de som var villige til å finne dem. "Fra timer og dager med visning virket periode 5 umulig," sa Gosper. Så i 1971, to år etter at spillet ble oppfunnet, ble ett funnet. Jakten på nye oscillatorer vokste til et hovedfokus i spillet, en søken styrket av fremkomsten av datateknologi. Beretninger om skjulte søk utført på kontordatamaskiner har blitt en hjørnestein i spillets folklore. "Mengden datatid som ble stjålet fra stormaskiner for bedrifter og universiteter var svimlende," sa Gosper.

Gjennom 1970-tallet fylte matematikere og hobbyfolk de andre korte periodene og fant en snert av lengre perioder. Etter hvert oppdaget matematikere en systematisk måte å bygge langtidsoscillatorer på. Men oscillatorer med perioder mellom 15 og 43 viste seg å være vanskelig å finne. "Folk har prøvd å finne ut av midten i årevis," sa Maia Karpovich, en doktorgradsstudent ved University of Maryland. Å fylle hullene tvang forskerne til å finne på en rekke nye teknikker som flyttet grensene for det man trodde var mulig med mobilautomater, som matematikere kaller utviklende rutenett som Life.

Nå har Karpovich og seks medforfattere annonsert i en desember fortrykk at de har funnet de to siste manglende periodene: 19 og 41. Med disse hullene fylt, er livet nå kjent for å være "omniperiodisk" - nevne et positivt heltall, og det eksisterer et mønster som gjentar seg etter så mange trinn.

Det spirende samfunnet viet til å studere livet, som inkluderer mange forskningsmatematikere, men også mange hobbyister, har funnet ikke bare oscillatorer, men alle slags nye mønstre. De har funnet mønstre som reiser over rutenettet, kalt romskip og mønstre som bygger andre mønstre: våpen, konstruktører og oppdrettere. De fant mønstre som beregner primtall, og til og med mønstre som kan utføre vilkårlig kompliserte algoritmer.

Oscillatorer med perioder kortere enn 15 kan bli funnet manuelt eller med rudimentære algoritmer som søker etter oscillatorer en celle om gangen. Men etter hvert som perioden blir større, øker kompleksiteten også, noe som gjør brute-force-søk langt mindre effektive. "I små perioder kan du søke direkte," sa Matthias Merzenich, en medforfatter av det nye papiret som oppdaget den første period-31-oscillatoren i 2010. "Men du kan egentlig ikke gå utover det. Du kan ikke bare velge en periode og søke etter den.» (Merzenich tok doktorgraden i matematikk fra Oregon State University i 2021, men jobber for tiden på en gård.)

I 1996 viste David Buckingham, en kanadisk frilans datakonsulent og livsentusiast som hadde søkt etter mønstre siden slutten av 1970-tallet, at det var mulig å konstruere oscillatorer fra periode 61 og høyere ved å sende et mønster rundt et lukket spor i en endeløs sløyfe . Ved å kontrollere lengden på løkken – og tiden det tok mønsteret å fullføre én rundtur – fant Buckingham ut at han kunne gjøre perioden så stor som han ville. "Det er kjemi uten morsomme lukter eller knust glass," sa han. "Som å bygge sammensetninger og deretter utforske interaksjonene mellom dem." Dette betydde at han med ett slag hadde kommet opp med en måte å konstruere oscillatorer med vilkårlig lange perioder, så lenge de var lengre enn 61.

Det var en rekke resultater på midten av 1990-tallet, da mange av de manglende oscillatorene mellom 15 og 61 ble oppdaget gjennom kreative kombinasjoner av kjente oscillatorer, som hadde fått en rekke fargerike navn. Catering ble kombinert med trafikklys, vulkaner spyttet ut gnister, og spisere spiste seilfly.

Ved begynnelsen av det 21. århundre var bare et dusin perioder fortsatt utestående. "Det virket veldig mulig å løse dette problemet," sa Merzenich. I 2013 forbedret en ny oppdagelse kalt Snark-sløyfen Buckinghams teknikk fra 1996 og senket grensen over som det var lett å konstruere oscillatorer fra 61 til 43. Dette etterlot bare fem manglende perioder. En til ble oppdaget i 2019, og to til i 2022, og etterlot bare 19 og 41 - begge førsteklasses. "Primer er vanskeligere fordi du ikke kan bruke små periodiske oscillatorer til å konstruere dem," sa Merzenich.

Mitchell Riley, en postdoktor ved New York University Abu Dhabi og en annen medforfatter av det nye papiret, har lenge vært fascinert av en type oscillator kalt en hassler. "Måten hasslers fungerer på er at du har et aktivt mønster i midten og noen stabile ting på utsiden som reagerer med det," forklarte Riley. De stabile tingene, kalt en katalysator, er der for å skyve det aktive mønsteret tilbake til sin opprinnelige tilstand.

Å designe dem er vanskelig. "Alle disse mønstrene er utrolig skjøre," sa Riley. "Hvis du setter en enkelt prikk malplassert, eksploderer de vanligvis bare."

Riley opprettet et program kalt Barrister for å se etter nye katalysatorer. «Det vi ser etter er stilleben som er robuste. Hele poenget er at vi vil at de skal samhandle med det som skjer i midten og deretter komme seg, sa Riley.

Riley matet katalysatorer som Barrister fant inn i et annet søkeprogram som paret dem med aktive mønstre. Dette førte mest til feil, sa han. "Det er ganske sjelden at en av disse katalysatorene overlever interaksjonen. Det er ingen garanti for suksess. Du bare krysser fingrene og håper at du treffer jackpotten. Det føles litt som gambling.»

Til slutt ga innsatsen hans resultater. Etter noen nestenulykker - og en modifikasjon av koden som utvidet søket til å inkludere symmetriske mønstre - fant han en katalysatorinteraksjon som kunne opprettholde en periode-19-oscillator. "Folk hadde prøvd alle slags veldig kompliserte søk med mange katalysatorer og mange sjeldne aktive ting i midten, men alt som var nødvendig var å finne denne nye tykke katalysatoren," sa Riley.

Den siste manglende perioden, 41, ble funnet av Nicolo Brown, en annen medforfatter, som fortsatt er en mastergrad i matematikk ved University of California, Santa Cruz. Brown brukte seilfly som katalysatorer, en idé først foreslått av Merzenich.

"Vi har oppdaget så mye dyp oppførsel de siste 10 årene," sa Karpovich. "Alle feirer i en uke - og går så videre til andre ting. Det er så mange andre problemer å løse.» Kan oscillatorer for en gitt periode gjøres mindre? Finnes det oscillatorer der hver enkelt celle svinger? Kan våpen lages med bestemte perioder? Kan romskip fåes til å reise med spesielle hastigheter?

Som Buckingham sa det, "Det er som å være et barn i en uendelig lekebutikk."