Livet utan död

Life without Death-mönster som skapar tre stegar och visar döden av två stegar genom att kollidera med en enda cell (två olika sätt), vridningen av en stege och döden av en stege genom att kollidera med en annan stege.

Antalet levande celler per generation av mönstret som visas ovan visar den monotona naturen av liv utan död.

Life without Death är en cellulär automat , liknande Conways Game of Life och andra livsliknande cellulära automatregler . I denna cellulära automat växer ett initialt frömönster enligt samma regel som i Conways Game of Life; dock, till skillnad från livet, krymper aldrig mönster. Regeln övervägdes ursprungligen av Toffoli & Margolus (1987), som kallade den "Bläckfläck"; den har också kallats "Flingor". Till skillnad från de mer komplexa mönstren som finns inom Conways Game of Life, innehåller Life without Death vanligtvis stillebensmönster , där ingen förändring sker, och stegmönster , som växer i en rak linje.

Regler

En cellulär automat är en typ av modell studerad i matematik och teoretisk biologi som består av ett regelbundet rutnät av celler, var och en i ett av ett ändligt antal tillstånd, såsom "på" och "av". Ett mönster i Life without Death cellulära automaten består av ett oändligt tvådimensionellt rutnät av celler, som var och en kan vara i ett av två tillstånd: döda eller levande. På motsvarande sätt kan det ses som en array av pixlar , som var och en kan vara svart och vit; i figurerna representerar de vita pixlarna levande celler, medan de svarta pixlarna representerar döda celler. Två av dessa celler anses vara grannar om de är vertikalt, horisontellt eller diagonalt intill varandra.

Varje sådant mönster ändras över en sekvens av tidssteg genom att tillämpa följande enkla regler samtidigt på alla celler i mönstret: varje cell som levde i det föregående mönstret förblir vid liv, varje död cell som har exakt 3 levande grannar blir själv levande, och varannan död cell förblir död. Det vill säga, i notationen som beskriver livsliknande cellulära automatregler , är det regel B3/S012345678: en levande cell föds när det finns 3 levande grannar, och en levande cell överlever med hur många grannar som helst.

Skott och stegar

Stillebensmönster är vanliga i Livet utan död: om det inte finns någon död cell med tre levande grannar kommer ett mönster att förbli oföränderligt för alla framtida tidssteg. Men eftersom en cell, en gång levande, förblir vid liv, växer uppsättningen av levande celler monotont under utvecklingen av ett mönster, och det kan inte finnas några oscillatorer (mönster som cirkulerar genom en upprepad sekvens av former), rymdskepp (mönster som håller samma form men byter position), eller de andra mer komplexa mönstren som finns inom Conways Game of Life.

Ett exempel på ett snabbt parasitskott som löper längs en långsammare stege. När spetsarna på skottet och stegen möts förstörs de båda och skapar en kaotisk röra och skickar två skott tillbaka nerför den ursprungliga stegen i motsatt riktning.

Istället är ett vanligt inslag i Life without Death-mönster närvaron av stegar , mönster som växer i en rak linje. En stege kommer att växa för evigt om den inte springer in i någon annan del av mönstret och blockeras eller om inte något mer snabbväxande mönster kör om den. Det vanligaste stegmönstret visas i figuren; vart tolfte steg visas samma form längst upp på stegen, fyra celler längre från stegens startposition. Hastigheten för stegens tillväxt är därför fyra celler per tolv steg, eller, i livsnotation, 4 c /12 = c /3; här c en enhet av avstånd per tidssteg. Ett annat vanligt mönster (kallat ett "parasitskott" av Gravner och Griffeath) avancerar dubbelt så snabbt, med hastighet 2 c /3, längs sidan av en stege, vilket till slut blockerar stegen och orsakar en kaotisk explosion.

Varierande stegar med andra hastigheter upptäcktes år 2000 av Dean Hickerson, tillsammans med några parasitskott som är långsammare än den vanligaste 2 c /3. Hickersons stegar växer med hastigheter 4 c /9, 4 c /10 och 4 c /13.

Simulering av kretsar

Stegarna i Livet utan död kan användas för att simulera godtyckliga booleska kretsar : närvaron eller frånvaron av en stege i en viss position kan användas för att representera en boolesk signal, och olika interaktioner mellan stegpar, eller mellan stegar och stillebensmönster , kan användas för att simulera "och", "eller" och "inte" -grindarna för boolesk logik, såväl som punkterna där två signaler korsar varandra. Därför är det P-komplett att simulera mönster i Life without Death-regeln, vilket innebär att det är osannolikt att det finns en parallell algoritm för en simulering som är betydligt snabbare än den som erhålls av en naiv parallell algoritm med en processor per cellulär automatcell och ett tidssteg per generation av mönstret.

Oändlig tillväxt

Frömönster i form av kulor med radie upp till tio leder vanligtvis till ett stillebensmönster ; Emellertid antyder Gravner att regeln är superkritisk, vilket betyder att större eller mindre symmetriska frön vanligtvis expanderar för alltid kaotiskt. Stegar är ett frekvent fenomen på gränserna för kaotiska tillväxtregioner.

Ett mönster i Livet utan död sägs fylla planet med positiv densitet om det finns någon radie r så att varje cell i planet så småningom är inom avståndet r från en levande cell. Frågan om huruvida sådana oändliga tillväxtmönster existerar ställdes som ett öppet problem av Gravner, Griffeath och Moore. De kaotiska mönstren som är vanliga i denna regel kan fylla planet, men de kan också lämna stora tomma rektangulära områden inramade av stegar, vilket gör att de misslyckas med densitetsvillkoret. Men 2009 hittade Dean Hickerson diagonalt expanderande mönster som så småningom sätter sig i en oändlig tillväxt under hög period, vilket löser det öppna problemet.

externa länkar

• A Way-Cool CyberFlake och Life Without Death (Revisited), från Primordial Soup Kitchen-webbplatsen för cellulära automater.
• Liv utan död på LifeWiki.