Stilleben (cellulär automat)

I Conways Game of Life och andra cellulära automater är ett stilleben ett mönster som inte förändras från en generation till nästa. Termen kommer från konstvärlden där en stilleben skildrar en livlös scen. I cellulära automater kan ett stilleben ses som en oscillator med enhetsperiod.

Klassificering

Pseudostilleben

Strikt stilleben

Ett pseudostilleben består av två eller flera intilliggande öar ( anslutna komponenter ) som kan delas upp (antingen individuellt eller som uppsättningar) i icke-samverkande underdelar, som också är stilleben. Detta kan jämföras med ett strikt stilleben , som kanske inte delas upp på detta sätt. Ett strikt stilleben kan bara ha en enda ö, eller så kan det ha flera öar som är beroende av varandra för stabilitet och kan därför inte brytas ner. Skillnaden mellan de två är inte alltid uppenbar, eftersom ett strikt stilleben kan ha flera sammankopplade komponenter som alla behövs för dess stabilitet. Det är dock möjligt att avgöra om ett stillebensmönster är ett strikt stilleben eller ett pseudostilleben i polynomtid genom att söka efter cykler i en tillhörande skevsymmetrisk graf .

Exempel

Det finns många naturligt förekommande stilleben i Conways Game of Life . Ett slumpmässigt initialt mönster kommer att lämna efter sig en hel del skräp, innehållande små oscillatorer och en stor variation av stilleben.

Det vanligaste stillebenet (dvs. som med största sannolikhet genereras från ett slumpmässigt initialtillstånd) är blocket . Ett par block placerade sida vid sida (eller bi-block ) är det enklaste pseudostilleben. Block används som komponenter i många komplexa enheter, ett exempel är Gosper glider gun .

Blockera

Bi-block

Det näst vanligaste stillebenet är kupan (eller bikupan ). Bikupor skapas ofta i (icke-interagerande) uppsättningar om fyra, i en formation som kallas en honungsfarm .

Bikupa

Honungsgård

Det tredje vanligaste stillebenet är limpan . Bröd finns ofta tillsammans i ett par som kallas en bi-limpa . Bi-loaves själva skapas ofta i en ytterligare (icke-interagerande) parning som kallas ett bageri . Två bagerier kan extremt sällan bildas bredvid varandra och bildar en uppsättning av fyra bröd som kallas en tetraloaf tillsammans med ytterligare två bi-limpor.

Limpa

Bi-limpa

Bageri

Ett badkar består av fyra levande celler placerade i en diamantform runt en central död cell. Att placera en extra levande cell diagonalt mot den centrala cellen ger ett annat stilleben, känd som en båt . Att placera ytterligare en levande cell på den motsatta sidan ger ännu ett stilleben, känt som ett skepp . En balja, en båt eller ett fartyg kan förlängas genom att lägga till ett par levande celler, för att ge en pråm , en långbåt respektive ett långskepp . Denna förlängning kan upprepas i oändlighet, för att ge godtyckligt stora strukturer.

Från vänster: badkar, pråm, långpråm, etc...

Från vänster: båt, långbåt, etc...

Från vänster: fartyg, långskepp, etc...

Ett par båtar kan kombineras för att ge ett annat stilleben som kallas båtslipsen ( en ordlek på fluga, som den ytligt liknar). På liknande sätt kan ett par fartyg kombineras till en fartygsslips .

Båtslips

Skeppsslips

Ätare

Fiskkrok (ätare1)

ätare 2

Stilleben kan användas för att modifiera eller förstöra andra föremål. Ett stilleben kallas en eater när det kan användas för att absorbera något annat mönster (ofta ett glidflygplan , rymdskepp eller skräp från en mer komplicerad reaktion) och återgår till sitt ursprungliga tillstånd efter kollisionen. Det finns många exempel, med det mest anmärkningsvärda är fiskkroken (även känd som eater 1 ), som kan absorbera flera typer av rymdskepp. En liknande enhet är " reflektorn ", som ändrar riktningen på ett inkommande rymdskepp. Oscillatorer med liknande egenskaper kan också kallas eaters eller reflektorer, men är svårare att applicera då de måste synkroniseras med mönstret de modifierar. Stillebensätare och reflektorer, å andra sidan, fungerar korrekt oavsett tidpunkten för mönstret de modifierar, så länge som successiva reaktioner inträffar med tillräckligt med separation i tid för att tillåta ätaren eller reflektorn att återställa sin ursprungliga form.

Uppräkning

Antalet strikta och pseudostilleben i Conways Game of Life som finns för ett givet antal levande celler har dokumenterats upp till ett värde av 34 (sekvenserna A019473 respektive A056613 i On - Line Encyclopedia of Integer Sequences (OEIS).

Levande celler	Strikta stilleben	Pseudostilleben	Exempel
1	0	0
2	0	0
3	0	0
4	2	0	Block, badkar
5	1	0	Båt
6	5	0	Pråm, bikupa, bärare, skepp, orm
7	4	0	Fiskkrok, limpa, långbåt, pyton
8	9	1	Kanot, mango, lång pråm, damm
9	10	1	Hatt, integralskylt
10	25	7	Block på bord, båtslips, ögla
11	46	16
12	121	55	Ship-tie
13	240	110
14	619	279	Bi-loaf
15	1 353	620
16	3,286	1 645
17	7,773	4 067
18	19 044	10,843
19	45,759	27 250	Eater 2
20	112,243	70,637
21	273,188	179 011
22	672,172	462 086
23	1,646,147	1,184,882
24	4,051,732	3,069,135
25	9,971,377	7,906,676
26	24,619,307	20,463,274
27	60 823 008	52,816,265
28	150,613,157	136,655,095
29	373,188,952	353,198,379
30	926,068,847	914,075,620
31	2,299,616,637	2,364,815,358
32	5,716,948,683	6,123,084,116
33	14,223,867,298	15,851,861,075
34	35,422,864,104	41,058,173,683

Densitet

Stilleben med maximal densitet 19x19 i Conways spel om livet

Stilleben med maximal densitet 20x20 i Conways spel om livet

Problemet med att förse en n×n-region med ett maximalt tätt stilleben har uppmärksammats som ett testfall för begränsningsprogrammering . Inom gränsen för ett oändligt stort rutnät kan inte mer än hälften av cellerna i planet vara levande. För finita kvadratiska rutnät kan större densiteter uppnås. Till exempel är stilleben med maximal densitet inom en 8×8 kvadrat ett vanligt rutnät med nio block, med densitet 36/64 = 0,5625. Optimala lösningar är kända för rutor i alla storlekar. Yorke-Smith tillhandahåller en lista över kända mönster med ändlig maximal densitet.