Stilleben (konfiguration av en cellulär automat)

Stilleben är en klass av konfigurationer i Life, Conways modell av en cellulär automat .

Beskrivning

I den mest allmänna formuleringen betyder begreppet "stilleben" detsamma som "stabil figur" - konfigurationen av "Livet" eller en annan cellulär automat som inte förändras i evolutionsprocessen [nb 1] . Med andra ord är stilleben en 1 [1] [2] [3 ] periodoscillator .

Terminologi: stilleben och pseudostilleben

Det finns flera termer som ligger nära i betydelse, och betecknar konfigurationer som inte förändras i evolutionsprocessen ( konfigurationer som är deras egna föräldrar ). Skillnaderna mellan dem är relaterade till svaret på följande frågor:

  1. Anses en konfiguration bestående av två oberoende stilleben (till exempel två block på tillräckligt stort avstånd från varandra) vara ett stilleben? [fyra]
  2. Är ett stilleben en konfiguration som består av två delar, som båda kan tas bort så att den andra delen förblir föräldern till sig själv?

De befintliga ordböckerna och onlineuppslagsverken [3] [5] [6] [7] tillhandahåller följande definitioner:

Den exakta definitionen av "stabilitet" är av intresse i samband med listning av stilleben: till exempel, enligt de givna definitionerna, är antalet stabila konfigurationer av storlek 8 (dvs. bestående av 8 levande celler) i "Life" oändligt , eftersom ett par block på valfritt avstånd från varandra är hållbart; antalet stilleben av begränsad storlek anses dock vara ändligt [5] [6] [7] .

Pseudo-stilleben i "Life". Att ta bort en av öarna påverkar inte stabiliteten på den andra ön.
"Strikt" stilleben. Stabiliteten på var och en av öarna beror på tillgången på den andra ön.

Antalet stilleben och pseudo-stilleben som inte är större än 24 celler är känt [7] [10] [11] .

Problemet med att bestämma typen av stabil konfiguration (stilleben, pseudostilleben) löses i polynomtid genom att söka efter cykler i en sammankopplad skev-symmetrisk graf [12] .

Stilleben i "Life"

I "Life" finns det många naturliga [13] stilleben.

Enkla exempel

Blockera

Det vanligaste stillebenet är ett block [14] [15] [16] - en konfiguration i form av en kvadrat på 2 × 2. Två block placerade i en 2 × 5 rektangel bildar ett biblock - den enklaste pseudo-destillationen liv. Block används som byggstenar i en mängd olika komplexa enheter, såsom Gosper glider gun [16] .

Hive

Det näst vanligaste stillebenet är en bikupa ( eng.  hive, beehive ). Bikupor visas ofta i fyror i en konfiguration som kallas bigård ( engelsk  honungsfarm ) [14] [15] [16] .

Loaf

Det tredje vanligaste stillebenet är en limpa ( eng.  loaf ). Bröd uppträder ofta i par ( engelska  bi-loaf ) [14] [15] [16] . I sin tur förekommer dubbla bröd också i par som kallas bagerier ( engelska  bakery ) [17] .

Lådor, pråmar, båtar, fartyg

Lådan ( eng.  tub ) består av fyra levande celler i von Neumann-kvarteret i den centrala döda cellen. Att lägga till en levande cell diagonalt till den centrala cellen förvandlar lådan till en båt ( engelsk  båt ), och om man lägger till en annan cell symmetriskt förvandlas den till ett skepp ( engelskt  skepp ) [18] . Den naturliga förlängningen av dessa tre konfigurationer ger en pråm ( engelsk  pråm ), en långbåt ( engelsk  long-boat ) respektive ett långskepp ( engelsk  long-ship ). Förlängningen kan fortsätta på obestämd tid [5] [6] [15] [16] .

Av två båtar kan man göra ett annat stilleben - en båtbåge ( English  boat tie ), och från två ships - en ship-bow ( engelsk  ship tie ) [5] [6] .

Andra stilleben

  • Kanot

  • Hangarfartyg

  • Integral tecken

  • Mango/cigarr

  • Damm

  • Orm

Devourers and Reflectors

Stilleben kan användas för att modifiera eller förstöra andra föremål. Eatern kan förstöra  rymdskeppet och återhämta sig från reaktionen. Reflektorn ( engelska reflector ) istället för att förstöra rymdfarkosten ändrar flygriktningen.  

Reflektorer och Devourers behöver inte vara stilleben.

  • Ätare

  • Fiskkrok / Eater-1

  • Devourer-2

Maximal densitet

Problemet med att placera ett stilleben med det maximala antalet celler i ett n  ×  n område har uppmärksammats av programmerare som ett begränsningsprogrammeringsproblem [19] [20] [21] [22] [23] . Eftersom storleken på regionen tenderar att vara oändlig, kan inte mer än 50% av cellerna vara vid liv [24] . I ändliga kvadratiska områden kan högre densiteter uppnås. Således är den maximala tätheten för ett stilleben i en 8 × 8 kvadrat 36/64 = 0,5625 - denna densitet tillhandahålls av ett prov bestående av nio block [19] För kvadrater upp till 20 × 20 är optimala lösningar kända [25 ] [26] .

  • Stilleben med maximal täthet i "Life"

  • 19x19

  • 20x20

Antal stilleben

Antalet stilleben och pseudo-stilleben i "Life" är känt upp till en storlek på 24 celler [27] [28] [29] .

Antal levande celler Antal stilleben Exempel
ett 0
2 0
3 0
fyra 2 block, låda
5 ett båt
6 5 pråm, hangarfartyg, bikupa, fartyg, orm
7 fyra fiskekrok, limpa, långbåt
åtta 9 kanot, mango, lång pråm, damm
9 tio integrerad tecken
tio 25 båt fören
elva 46
12 121 fartygets för
13 240
fjorton 619 dubbel limpa
femton 1353
16 3286
17 7773
arton 19044
19 45759 ätare 2
tjugo 112243
21 273188
22 672172
23 1646147
24 4051711

Fotnoter

  1. ↑ För mer rigorösa definitioner, se Terminologi.

Anteckningar

  1. ↑ 1 2 Stadig . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 10 februari 2013.
  2. ↑ 1 2 Stabil (nedlänk) . livslexikon. Hämtad 11 augusti 2013. Arkiverad från originalet 20 februari 2009. 
  3. ↑ 1 2 Eric Weisstein. stilleben . Livets skattkammare CA. Hämtad: 11 augusti 2013.  (inte tillgänglig länk)
  4. ↑ Om svaret på denna fråga är ja, då är antalet stilleben med ett begränsat antal celler oändligt.
  5. ↑ 1 2 3 4 Nikolai Belyuchenko. Livets ordbok . Arkiverad från originalet den 10 oktober 2012.
  6. ↑ 1 2 3 4 Stephen A. Silver. Livslexikon  . _ Arkiverad från originalet den 26 maj 2013.
  7. ↑ 1 2 3 4 5 Stilleben . conwaylife.com. Hämtad 11 augusti 2013. Arkiverad från originalet 30 juli 2013.
  8. ↑ Stilleben . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 10 februari 2013.
  9. ↑ Stilleben (inte tillgänglig länk) . livslexikon. Hämtad 11 augusti 2013. Arkiverad från originalet 20 februari 2009. 
  10. ↑ 1 2 Pseudostilleben . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 6 maj 2019.
  11. ↑ 1 2 Pseudostilleben (inte tillgänglig länk) . livslexikon. Hämtad 11 augusti 2013. Arkiverad från originalet 3 december 2014. 
  12. ↑ Cook, Matthew (2003). "Stillebenteori". Nya konstruktioner i cellulära automater . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93-118.
  13. ↑ Ett naturligt prov är ett objekt som förekommer relativt ofta under utvecklingen av en slumpmässig konfiguration.
  14. ↑ 1 2 3 Achim Flammenkamp. Topp 100 av Game-of-Life Ash Objects . Hämtad 5 november 2008. Arkiverad från originalet 22 oktober 2008.
  15. ↑ 1 2 3 4 The Game of Life (Gardner recension) . Hämtad 11 augusti 2013. Arkiverad från originalet 18 oktober 2012.
  16. ↑ 1 2 3 4 5 Klumova I. N. Spelet "Livet"  // Kvant . - 1974. - Nr 9 . - S. 26-30 .
  17. ↑ Bageri . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 6 maj 2019.
  18. ↑ Inte att förväxla med rymdskepp .
  19. ↑ 1 2 Bosch, RA Heltalsprogrammering och Conways spel om livet  (obestämd)  // SIAM Review. - 1999. - T. 41 , nr 3 . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Stabila mönster för maximal densitet i varianter av Conways spel om livet  //  Operations Research Letters : journal. - 2000. - Vol. 27 , nr. 1 . - S. 7-11 . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ↑ Smith, Barbara M. Principer och praxis för begränsningsprogrammering - CP 2002   : tidskrift . - Springer-Verlag, 2002. - Vol. 2470 . - S. 89-94 . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Trick, Michael. Begränsningsprogrammering och hybridformuleringar för tre Life-designer  //  Annals of Operations Research : journal. - 2004. - Vol. 130 , nr. 1-4 . - S. 41-56 . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Tillämpa ad-hoc globala begränsningar med fallbegränsningen på stilleben  //  Begränsningar: journal. - 2006. - Vol. 11 , nr. 2-3 . - S. 91-114 . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). "Täthetsproblemet med stilleben och dess generaliseringar". Voronois inverkan på modern vetenskap, bok I. Proc. Inst. Matematik. Nat. Acad. sci. Ukraina, vol. 21.pp. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho och D. Niso. Om den praktiska användningen av variabel eliminering i problem med optimeringsproblem: "Still-life" som fallstudie  //  Journal of Artificial Intelligence Research : journal. - 2005. - Vol. 23 . - s. 421-440 . Arkiverad från originalet den 16 juli 2011.
  26. ↑ Neil Yorke-Smith. Stilleben med maximal densitet . Artificiell intelligens Center . SRI International. Hämtad 11 augusti 2013. Arkiverad från originalet 19 maj 2013.
  27. ↑ Antal stabila n-cellsmönster ("stilleben") i Conways game of Life
  28. ↑ Antal n-cellade pseudo-stilleben i Conways game of Life
  29. ↑ Niemiec, Mark D. Livsstilleben . Arkiverad från originalet den 21 januari 2013.

Externa länkar

 Conways Game of Life och andra cellulära automater
Konfigurationsklasser
Konfigurationer
Villkor
Andra rymdskepp på ett
tvådimensionellt gitter
Levande
Övrig
Endimensionell rymdfarkost
Programvara och algoritmer
  • Golly
  • Mireks
  • hashlife
KA-forskare