Stilleben (konfiguration af en cellulær automat)

Stilleben er en klasse af konfigurationer i Life, Conways model af en cellulær automat .

Beskrivelse

I den mest generelle formulering betyder begrebet "stilleben" det samme som "stabil figur" - konfigurationen af ​​"Livet" eller en anden cellulær automat, der ikke ændrer sig i evolutionsprocessen [nb 1] . Med andre ord er stilleben en 1 [1] [2] [3] periode oscillator .

Terminologi: stilleben og pseudo-stilleben

Der er flere begreber, der er tætte i betydningen, og betegner konfigurationer, der ikke ændrer sig i evolutionsprocessen ( konfigurationer, der er deres egne forældre ). Forskellene mellem dem er relateret til svaret på følgende spørgsmål:

  1. Anses en konfiguration bestående af to uafhængige stilleben (f.eks. to blokke i tilstrækkelig stor afstand fra hinanden) for at være et stilleben? [fire]
  2. Er et stilleben en konfiguration bestående af to dele, som begge kan fjernes, så den anden del forbliver forælderen til sig selv?

De eksisterende ordbøger og online encyklopædier [3] [5] [6] [7] giver følgende definitioner:

Den nøjagtige definition af "stabilitet" er af interesse i forbindelse med opremsning af stilleben: for eksempel, ifølge de givne definitioner, er antallet af stabile konfigurationer af størrelse 8 (dvs. bestående af 8 levende celler) i "Life" uendeligt , da et par blokke i enhver afstand fra hinanden er stabile; antallet af stilleben af ​​begrænset størrelse anses dog for at være begrænset [5] [6] [7] .

Pseudo-stilleben i "Life". Fjernelse af en af ​​øerne påvirker ikke stabiliteten af ​​den anden ø.
"Streng" stilleben. Stabiliteten af ​​hver af øerne afhænger af tilgængeligheden af ​​den anden ø.

Antallet af stilleben og pseudo-stilleben, der ikke er større end 24 celler, er kendt [7] [10] [11] .

Problemet med at bestemme typen af ​​stabil konfiguration (stilleben, pseudo-stilleben) løses i polynomisk tid ved at søge efter cyklusser i en forbundet skæv-symmetrisk graf [12] .

Stilleben i "Life"

I "Life" er der mange naturlige [13] stilleben.

Simple eksempler

Bloker

Det mest almindelige stilleben er en blok [14] [15] [16] - en konfiguration i form af en kvadratisk 2 × 2. To blokke placeret i et 2 × 5 rektangel danner en bi-blok - den enkleste pseudo-still. liv. Blokke bruges som byggeklodser i en række komplekse enheder, såsom Gosper svæveflyvepistolen [16] .

Hive

Det næstmest almindelige stilleben er en bikube ( eng.  hive, beehive ). Nældefeber optræder ofte i fire i en konfiguration kaldet bigård ( engelsk  honningfarm ) [14] [15] [16] .

Brød

Det tredje mest almindelige stilleben er et brød ( eng.  loaf ). Brød optræder ofte i par ( engelsk  bi-loaf ) [14] [15] [16] . Til gengæld optræder dobbeltbrød også parvis kaldet bagerier ( engelsk  bakeri ) [17] .

Kasser, pramme, både, skibe

Kassen ( eng.  tub ) består af fire levende celler i von Neumann-kvarteret i den centrale døde celle. Tilføjelse af en levende celle diagonalt til den centrale celle gør kassen til en båd ( engelsk  båd ), og tilføjelse af en anden celle forvandler den symmetrisk til et skib ( engelsk  skib ) [18] . Den naturlige forlængelse af disse tre konfigurationer giver henholdsvis en pram ( engelsk  pram ), en lang båd ( engelsk  langbåd ) og et langskib ( engelsk  langskib ). Forlængelsen kan fortsættes i det uendelige [5] [6] [15] [16] .

Fra to både kan man lave endnu et stilleben - en bådstævn ( engelsk  bådbind ), og fra to skibe - en skibsstævn ( engelsk  skibsstævn ) [5] [6] .

Andre stilleben

  • Kano

  • Hangarskib

  • Integral tegn

  • Mango / Cigar

  • Dam

  • Slange

Devourers and Reflectors

Stilleben kan bruges til at ændre eller ødelægge andre objekter. Eateren er i stand  til at ødelægge rumskibet og komme sig efter reaktionen. Reflektoren ( engelsk  reflector ) i stedet for at ødelægge rumfartøjet ændrer retningen på dets flyvning.

Reflekser og Devourers behøver ikke at være stilleben.

  • Spiser

  • Fiskekrog / Eater-1

  • Devourer-2

Maksimal tæthed

Problemet med at placere et stilleben med det maksimale antal celler i et n  ×  n område har tiltrukket programmørers opmærksomhed som et begrænsningsprogrammeringsproblem [19] [20] [21] [22] [23] . Da regionens størrelse har en tendens til uendelig, kan ikke mere end 50% af cellerne være i live [24] . I endelige kvadratiske områder kan højere tætheder opnås. Den maksimale tæthed af et stilleben i en 8 × 8 kvadrat er således 36/64 = 0,5625 - denne tæthed er tilvejebragt af en prøve bestående af ni blokke [19] For kvadrater op til 20 × 20 kendes optimale løsninger [25 ] [26] .

  • Stilleben med maksimal tæthed i "Life"

  • 19x19

  • 20x20

Antal stilleben

Antallet af stilleben og pseudo-stilleben i "Life" er kendt op til en størrelse på 24 celler [27] [28] [29] .

Antal levende celler Antal stilleben Eksempler
en 0
2 0
3 0
fire 2 blok, kasse
5 en båd
6 5 pram, hangarskib, bikube, skib, slange
7 fire fiskekrog, brød, lang båd
otte 9 kano, mango, lang pram, dam
9 ti integraltegn
ti 25 bådstævn
elleve 46
12 121 skibs stævn
13 240
fjorten 619 dobbelt brød
femten 1353
16 3286
17 7773
atten 19044
19 45759 spiser 2
tyve 112243
21 273188
22 672172
23 1646147
24 4051711

Fodnoter

  1. ↑ For mere stringente definitioner, se Terminologi.

Noter

  1. ↑ 1 2 Stabil . Livsordbog. Hentet 11. august 2013. Arkiveret fra originalen 10. februar 2013.
  2. ↑ 1 2 Stabil (downlink) . livsleksikon. Hentet 11. august 2013. Arkiveret fra originalen 20. februar 2009. 
  3. ↑ 1 2 Eric Weisstein. stilleben . Treasure Trove of Life CA. Hentet: 11. august 2013.  (ikke tilgængeligt link)
  4. ↑ Hvis svaret på dette spørgsmål er ja, så er antallet af stilleben med et begrænset antal celler uendeligt.
  5. ↑ 1 2 3 4 Nikolai Belyuchenko. Livsordbog . Arkiveret fra originalen den 10. oktober 2012.
  6. ↑ 1 2 3 4 Stephen A. Sølv. Livsleksikon  . _ Arkiveret fra originalen den 26. maj 2013.
  7. ↑ 1 2 3 4 5 Stilleben . conwaylife.com. Hentet 11. august 2013. Arkiveret fra originalen 30. juli 2013.
  8. ↑ Stilleben . Livsordbog. Hentet 11. august 2013. Arkiveret fra originalen 10. februar 2013.
  9. ↑ Stilleben (utilgængeligt link) . livsleksikon. Hentet 11. august 2013. Arkiveret fra originalen 20. februar 2009. 
  10. ↑ 1 2 Pseudo-stilleben . Livsordbog. Hentet 11. august 2013. Arkiveret fra originalen 6. maj 2019.
  11. ↑ 1 2 Pseudo-stilleben (utilgængeligt link) . livsleksikon. Hentet 11. august 2013. Arkiveret fra originalen 3. december 2014. 
  12. ↑ Cook, Matthew (2003). "Stilleben teori". Nye konstruktioner i cellulære automater . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93-118.
  13. ↑ En naturlig prøve er et objekt, der forekommer relativt ofte i processen med udvikling af en tilfældig konfiguration.
  14. ↑ 1 2 3 Achim Flammenkamp. Top 100 af Game-of-Life Ash Objects . Hentet 5. november 2008. Arkiveret fra originalen 22. oktober 2008.
  15. ↑ 1 2 3 4 The Game of Life (Gardner anmeldelse) . Hentet 11. august 2013. Arkiveret fra originalen 18. oktober 2012.
  16. ↑ 1 2 3 4 5 Klumova I. N. Spil "Livet"  // Kvant . - 1974. - Nr. 9 . - S. 26-30 .
  17. ↑ Bageri . Livsordbog. Hentet 11. august 2013. Arkiveret fra originalen 6. maj 2019.
  18. ↑ Må ikke forveksles med rumfartøjer .
  19. ↑ 1 2 Bosch, RA Heltalsprogrammering og Conways game of Life  (ubestemt)  // SIAM Review. - 1999. - T. 41 , nr. 3 . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Maksimal tæthed stabile mønstre i varianter af Conways game of Life  //  Operations Research Letters : journal. - 2000. - Vol. 27 , nr. 1 . - S. 7-11 . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ↑ Smith, Barbara M. Principper og praksis for begrænsningsprogrammering - CP 2002   : tidsskrift . - Springer-Verlag, 2002. - Vol. 2470 . - S. 89-94 . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Trick, Michael. Begrænsningsprogrammering og hybride formuleringer til tre Life-designs  //  Annals of Operations Research : journal. - 2004. - Bd. 130 , nr. 1-4 . - S. 41-56 . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Anvendelse af ad-hoc globale begrænsninger med case-begrænsningen til stilleben  //  Constraints : journal. - 2006. - Bd. 11 , nr. 2-3 . - S. 91-114 . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). "Stillebens tæthedsproblemet og dets generaliseringer". Voronois indvirkning på moderne videnskab, bog I. Proc. Inst. Matematik. Nat. Acad. sci. Ukraine, vol. 21.pp. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho og D. Niso. Om den praktiske brug af variabel eliminering i problemer med begrænsningsoptimering: 'Still-life' som et casestudie  //  Journal of Artificial Intelligence Research : journal. - 2005. - Bd. 23 . - S. 421-440 . Arkiveret fra originalen den 16. juli 2011.
  26. ↑ Neil Yorke-Smith. Stilleben med maksimal tæthed . Center for kunstig intelligens . SRI International. Hentet 11. august 2013. Arkiveret fra originalen 19. maj 2013.
  27. ↑ Antal stabile n-cellede mønstre ("stilleben") i Conways game of Life
  28. ↑ Antal n-cellede pseudo-stilleben i Conways game of Life
  29. ↑ Niemiec, Mark D. Life Still-Lifes . Arkiveret fra originalen den 21. januar 2013.

Eksterne links

 Conways Game of Life og andre cellulære automater
Konfigurationsklasser
Konfigurationer
Vilkår
Andre rumfartøjer på et
todimensionelt gitter
Livsagtig
Andet
Et-dimensionelt rumfartøj
Software og algoritmer
  • Golly
  • Mireks
  • hashlife
KA-forskere