Maths "Game of Life" avslöjar långsökta återkommande mönster | Quanta Magazine

1969 utarbetade den brittiske matematikern John Conway en förbluffande enkel uppsättning regler för att skapa komplext beteende. Hans Game of Life, ofta kallad Livet, utspelar sig på ett oändligt kvadratiskt rutnät av celler. Varje cell kan vara antingen "levande" eller "död". Rutnätet utvecklas över en serie av varv (eller "generationer"), där varje cells öde bestäms av de åtta celler som omger den. Reglerna är följande:

1. Födelse: En död cell med exakt tre levande grannar blir levande.
2. Överlevnad: En levande cell med två eller tre levande grannar förblir vid liv.
3. Död: En levande cell med färre än två eller fler än tre levande grannar dör.

Dessa enkla regler skapar en häpnadsväckande mångfald av mönster, eller "livsformer", som utvecklas från de många olika möjliga startkonfigurationerna av rutnätet. Älskare av spelet har räknat och taxonomiserat dessa mönster i en ständigt växande online katalog. Conway upptäckte ett mönster som kallas blinker, som pendlar mellan två tillstånd.

Nästa år hittade han ett mycket mer komplicerat mönster som kallas pulsar, som pendlar mellan tre olika tillstånd.

Strax efter att oscillatorer upptäcktes, undrade spelets tidiga upptäcktsresande om det finns oscillatorer från varje period. "Först såg vi bara perioderna 1, 2, 3, 4 och 15," sa datorprogrammeraren och matematikern Bill Gosper, som skulle fortsätta att upptäcka 17 olika nya oscillatorer under de kommande decennierna. Period 15-oscillatorer (visas nedan) kom upp förvånansvärt ofta i slumpmässiga sökningar.

Överraskningar lurade för dem som var villiga att hitta dem. "Från timmar och dagar av visning verkade period 5 omöjlig," sa Gosper. Sedan 1971, två år efter att spelet uppfanns, hittades ett. Jakten på nya oscillatorer växte till ett stort fokus i spelet, en strävan som förstärktes av tillkomsten av datorteknik. Berättelser om hemliga sökningar utförda på kontorsdatorer har blivit en hörnsten i spelets folklore. "Mängden datortid som stulits från stordatorer för företag och universitet var svindlande," sa Gosper.

Under hela 1970-talet fyllde matematiker och hobbyister i de andra korta perioderna och hittade en smått med längre perioder. Så småningom upptäckte matematiker ett systematiskt sätt att bygga långtidsoscillatorer. Men oscillatorer med perioder mellan 15 och 43 visade sig vara svåra att hitta. "Folk har försökt komma på mitten i flera år", sa Maia Karpovich, en doktorand vid University of Maryland. Att fylla i luckorna tvingade forskare att drömma om en rad nya tekniker som tänjde på gränserna för vad man trodde var möjligt med cellulära automater, som matematiker kallar utvecklande rutnät som Life.

Nu har Karpovich och sex medförfattare meddelat i en Förtryck i december att de har hittat de två sista saknade perioderna: 19 och 41. Med dessa luckor fyllda är livet nu känt för att vara "omniperiodiskt" - nämn ett positivt heltal, och det finns ett mönster som upprepar sig efter så många steg.

Det växande samhället som ägnar sig åt att studera livet, som inkluderar många forskningsmatematiker men också många hobbyister, har hittat inte bara oscillatorer utan alla möjliga nya mönster. De har hittat mönster som reser över nätet, dubbade rymdskepp och mönster som bygger andra mönster: vapen, konstruktörer och uppfödare. De hittade mönster som beräknar primtal, och till och med mönster som kan exekvera godtyckligt komplicerade algoritmer.

Oscillatorer med perioder kortare än 15 kan hittas manuellt eller med rudimentära algoritmer som söker efter oscillatorer en cell i taget. Men när perioden blir större, blir komplexiteten också större, vilket gör sökningar med brute force mycket mindre effektiva. "Under små perioder kan du söka direkt," sa Matthias Merzenich, en medförfattare till den nya tidningen som upptäckte den första period-31-oscillatorn 2010. "Men du kan inte gå längre än så. Du kan inte bara välja en period och söka efter den." (Merzenich tog sin doktorsexamen i matematik från Oregon State University 2021, men arbetar för närvarande på en gård.)

1996 visade David Buckingham, en kanadensisk frilansande datorkonsult och livsentusiast som hade letat efter mönster sedan slutet av 1970-talet, att det var möjligt att konstruera oscillatorer från period 61 och högre genom att skicka ett mönster runt ett slutet spår i en oändlig slinga . Genom att kontrollera längden på slingan - och den tid det tog mönstret att genomföra en rundresa - fann Buckingham att han kunde göra perioden så stor som han ville. "Det är kemi utan roliga dofter eller trasiga glas," sa han. "Som att bygga föreningar och sedan utforska interaktionerna mellan dem." Detta innebar att han i ett slag hade kommit på ett sätt att konstruera oscillatorer med godtyckligt långa perioder, så länge de var längre än 61.

Det fanns en mängd resultat i mitten av 1990-talet, när många av de saknade oscillatorerna mellan 15 och 61 upptäcktes genom kreativa kombinationer av kända oscillatorer, som hade fått en mängd färgglada namn. Matserveringar kombinerades med trafikljus, vulkaner spottade ut gnistor och ätare åt segelflygplan.

Vid 21-talets början var bara ett dussin perioder fortfarande utestående. "Det verkade mycket möjligt att lösa det här problemet," sa Merzenich. 2013 förbättrades en ny upptäckt kallad Snark-slingan på Buckinghams teknik från 1996 och sänkte gränsen över vilken det var lätt att konstruera oscillatorer från 61 till 43. Detta lämnade bara fem saknade perioder. En till upptäcktes 2019, och två till 2022, vilket bara lämnade 19 och 41 - båda prime. "Prime är svårare eftersom du inte kan använda små periodiska oscillatorer för att konstruera dem," sa Merzenich.

Mitchell Riley, en postdoktor vid New York University Abu Dhabi och en annan medförfattare till det nya dokumentet, har länge varit fascinerad av en typ av oscillator som kallas en hassler. "Sättet som Hasslers arbetar på är att du har ett aktivt mönster i mitten och några stabila saker på utsidan som reagerar med det," förklarade Riley. De stabila sakerna, som kallas en katalysator, är till för att knuffa tillbaka det aktiva mönstret till sitt ursprungliga tillstånd.

Att designa dem är svårt. "Alla dessa mönster är otroligt ömtåliga," sa Riley. "Om du sätter en enda prick på plats, exploderar de vanligtvis bara."

Riley skapade ett program som heter Barrister för att leta efter nya katalysatorer. "Vad vi letar efter är stilleben som är robusta. Hela poängen är att vi vill att de ska interagera med vad som händer i mitten och sedan återhämta sig, säger Riley.

Riley matade katalysatorer som Barrister hittade i ett annat sökprogram som parade dem med aktiva mönster. Detta ledde mest till misslyckanden, sa han. "Det är ganska sällsynt att en av dessa katalysatorer överlever interaktionen. Det finns ingen garanti för framgång. Man håller liksom bara tummarna och hoppas att man vinner jackpotten. Det känns lite som att spela.”

Så småningom gav hans satsning resultat. Efter några nära misstag – och en modifiering av koden som utökade sökningen till att inkludera symmetriska mönster – hittade han en katalysatorinteraktion som kunde upprätthålla en period-19-oscillator. "Människor hade försökt alla typer av riktigt komplicerade sökningar med massor av katalysatorer och massor av sällsynta aktiva saker i mitten, men allt som behövdes var att hitta den här nya chunky katalysatorn," sa Riley.

Den sista saknade perioden, 41, hittades av Nicolo Brown, en annan medförfattare, som fortfarande är en grundutbildning i matematik vid University of California, Santa Cruz. Brown använde segelflygplan som katalysatorer, en idé som först föreslogs av Merzenich.

"Vi har upptäckt så mycket djupt beteende under de senaste 10 åren," sa Karpovich. "Alla firar i en vecka - och går sedan vidare till andra saker. Det finns så många andra problem att lösa.” Kan oscillatorer för en given period göras mindre? Kan man hitta oscillatorer där varje enskild cell svänger? Kan vapen tillverkas med speciella perioder? Kan rymdskepp fås att resa med speciella hastigheter?

Som Buckingham uttryckte det, "Det är som att vara ett barn i en oändlig leksaksaffär."