Zátiší (konfigurace celulárního automatu)

Zátiší je třída konfigurací v Life, Conwayově modelu buněčného automatu .

Popis

V nejobecnější formulaci pojem „zátiší“ znamená totéž co „stabilní postava“ – konfigurace „Života“ nebo jiného buněčného automatu, který se v procesu evoluce nemění [nb 1] . Jinými slovy, zátiší je 1 [1] [2] [3] periodický oscilátor .

Terminologie: zátiší a pseudozátiší

Existuje několik termínů, které jsou si blízkého významu a označují konfigurace, které se v procesu evoluce nemění ( konfigurace, které jsou jejich vlastními rodiči ). Rozdíly mezi nimi souvisí s odpovědí na následující otázky:

  1. Je konfigurace sestávající ze dvou nezávislých zátiší (například dvou bloků v dostatečně velké vzdálenosti od sebe) považována za zátiší? [čtyři]
  2. Je zátiší konfigurací sestávající ze dvou částí, z nichž každá může být odstraněna, takže druhá část zůstane sama sobě rodičem?

Stávající slovníky a online encyklopedie [3] [5] [6] [7] poskytují následující definice:

Přesná definice „stability“ je zajímavá v souvislosti s výčtem zátiší: například podle uvedených definic je počet stabilních konfigurací velikosti 8 (tj. sestávajících z 8 živých buněk) v „Life“ nekonečný. , protože dvojice bloků v jakékoli vzdálenosti od sebe je udržitelná; počet zátiší omezené velikosti je však považován za konečný [5] [6] [7] .

Pseudozátiší v "Životě". Odstranění jednoho z ostrovů neovlivní stabilitu druhého ostrova.
"Přísné" zátiší. Stabilita každého z ostrovů závisí na dostupnosti druhého ostrova.

Je znám počet zátiší a pseudozátiší ne větších než 24 buněk [7] [10] [11] .

Problém určení typu stabilní konfigurace (zátiší, pseudozátiší) je řešen v polynomiálním čase hledáním cyklů v spojeném šikmo symetrickém grafu [12] .

Zátiší v "Life"

V „Životě“ je mnoho přirozených [13] zátiší.

Jednoduché příklady

Blokovat

Nejrozšířenějším zátiším je kvádr [14] [15] [16] - konfigurace ve tvaru čtverce 2 × 2. Dva kvádry umístěné do obdélníku 2 × 5 tvoří biblok - nejjednodušší pseudozátiší život. Bloky se používají jako stavební bloky v různých složitých zařízeních, jako je kluzák Gosper [16] .

Úl

Druhým nejčastějším zátiším je úl ( angl.  hive, beehive ). Úly se často objevují po čtyřech v konfiguraci zvané apiary ( anglicky  honey farm ) [14] [15] [16] .

Bochník

Třetím nejčastějším zátiším je bochník ( angl.  bochník ). Bochníky se často objevují ve dvojicích ( anglicky  bi-loaf ) [14] [15] [16] . Dvojité bochníky se zase objevují ve dvojicích zvaných bakeries ( anglicky  bakery ) [17] .

Bedny, čluny, čluny, lodě

Schránka ( angl.  tub ) se skládá ze čtyř živých buněk ve von Neumannově sousedství centrální mrtvé buňky. Přidáním jedné živé buňky diagonálně k centrální buňce se z krabice stane člun ( anglicky  boat ) a přidáním další buňky se symetricky promění v loď ( anglicky  ship ) [18] . Přirozené prodloužení těchto tří konfigurací dává člun ( anglicky  barge ), dlouhé lodi ( anglicky  long-boat ) a dlouhé lodi ( anglicky  long-ship ). V prodlužování lze pokračovat donekonečna [5] [6] [15] [16] .

Ze dvou lodí můžete vyrobit další zátiší - lodní příď ( anglicky  boat tie ), a ze dvou lodí - lodní příď ( anglicky  ship tie ) [5] [6] .

Další zátiší

  • Kánoe

  • Letadlová loď

  • Integrální znak

  • Mango / Doutník

  • Rybník

  • Had

Požírače a reflektory

Zátiší lze použít k úpravě nebo zničení jiných předmětů. Požírač je schopen zničit vesmírnou loď a  zotavit se z reakce. Reflektor ( anglicky reflektor ) místo zničení kosmické lodi mění směr jejího letu.  

Reflektory a Devourers nemusí být zátiší.

  • Jedlíci

  • Rybí háček / Jedlík-1

  • Požírač-2

Maximální hustota

Problém umístění zátiší s maximálním počtem buněk v oblasti n  ×  n přitáhl pozornost programátorů jako problém programování s omezením [19] [20] [21] [22] [23] . Protože velikost oblasti má tendenci k nekonečnu, nemůže být naživu více než 50 % buněk [24] . V konečných čtvercových oblastech lze dosáhnout vyšších hustot. Maximální hustota zátiší ve čtverci 8 × 8 je tedy 36/64 = 0,5625 – tuto hustotu poskytuje vzorek skládající se z devíti bloků [19] Pro čtverce do 20 × 20 jsou známa optimální řešení [25 ] [26] .

  • Zátiší maximální hustoty v "Life"

  • 19x19

  • 20x20

Počet zátiší

Počet zátiší a pseudozátiší v „Life“ je znám až do velikosti 24 buněk [27] [28] [29] .

Počet živých buněk Počet zátiší Příklady
jeden 0
2 0
3 0
čtyři 2 blok, krabice
5 jeden loď
6 5 člun, letadlová loď, úl, loď, had
7 čtyři rybářský háček, bochník, dlouhá loď
osm 9 kánoe, mango, dlouhá bárka, rybník
9 deset integrální znak
deset 25 lodní příď
jedenáct 46
12 121 lodní příď
13 240
čtrnáct 619 dvojitý bochník
patnáct 1353
16 3286
17 7773
osmnáct 19044
19 45759 jedlík 2
dvacet 112243
21 273188
22 672172
23 1646147
24 4051711

Poznámky pod čarou

  1. ↑ Přesnější definice viz Terminologie.

Poznámky

  1. ↑ 1 2 Stabilní . Slovník života. Získáno 11. srpna 2013. Archivováno z originálu 10. února 2013.
  2. ↑ 1 2 Stabilní (downlink) . životní lexikon. Získáno 11. srpna 2013. Archivováno z originálu dne 20. února 2009. 
  3. ↑ 1 2 Eric Weisstein. zátiší . Treasure Trove of Life CA. Staženo: 11. srpna 2013.  (nedostupný odkaz)
  4. ↑ Pokud je odpověď na tuto otázku ano, pak je počet zátiší s omezeným počtem buněk nekonečný.
  5. ↑ 1 2 3 4 Nikolaj Beljučenko. Slovník života . Archivováno z originálu 10. října 2012.
  6. ↑ 1 2 3 4 Stephen A. Silver. Lexikon  života . Archivováno z originálu 26. května 2013.
  7. ↑ 1 2 3 4 5 Zátiší . conwaylife.com. Získáno 11. srpna 2013. Archivováno z originálu 30. července 2013.
  8. ↑ Zátiší . Slovník života. Získáno 11. srpna 2013. Archivováno z originálu 10. února 2013.
  9. ↑ Zátiší (nedostupný odkaz) . životní lexikon. Získáno 11. srpna 2013. Archivováno z originálu dne 20. února 2009. 
  10. ↑ 1 2 Pseudozátiší . Slovník života. Získáno 11. srpna 2013. Archivováno z originálu 6. května 2019.
  11. ↑ 1 2 Pseudozátiší (nedostupný odkaz) . životní lexikon. Získáno 11. srpna 2013. Archivováno z originálu 3. prosince 2014. 
  12. ↑ Cook, Matthew (2003). "Teorie zátiší". Nové konstrukce v celulárních automatech . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. str. 93-118.
  13. ↑ Přírodní vzorek je objekt, který se vyskytuje relativně často v procesu vývoje náhodné konfigurace.
  14. ↑ 1 2 3 Achim Flammenkamp. 100 nejlepších objektů Ash z Game-of-Life . Získáno 5. listopadu 2008. Archivováno z originálu 22. října 2008.
  15. ↑ 1 2 3 4 The Game of Life (Gardnerova recenze) . Získáno 11. srpna 2013. Archivováno z originálu 18. října 2012.
  16. ↑ 1 2 3 4 5 Klumová I. N. Hra "Život"  // Kvant . - 1974. - č. 9 . - S. 26-30 .
  17. ↑ Pekárna . Slovník života. Získáno 11. srpna 2013. Archivováno z originálu 6. května 2019.
  18. ↑ Nezaměňovat s kosmickou lodí .
  19. ↑ 1 2 Bosch, RA Celočíselné programování a Conwayova hra života  (na neurčito)  // Recenze SIAM. - 1999. - T. 41 , č. 3 . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Maximální hustota stabilní vzory ve variantách Conwayovy hry Life  //  Operations Research Letters : deník. - 2000. - Sv. 27 , č. 1 . - str. 7-11 . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ↑ Smith, Barbara M. Principles and Practice of Constraint Programming - CP 2002   : journal . - Springer-Verlag, 2002. - Sv. 2470 . - str. 89-94 . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Trik, Michaele. Programování omezení a hybridní formulace pro tři návrhy Life  //  Annals of Operations Research : deník. - 2004. - Sv. 130 , č. 1-4 . - str. 41-56 . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Použití ad-hoc globálních omezení s omezením případu na zátiší  //  Constraints: journal. - 2006. - Sv. 11 , č. 2-3 . - str. 91-114 . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). „Problém hustoty zátiší a jeho zobecnění“. Voronoiův dopad na moderní vědu, kniha I. Proč. Inst. Matematika. Nat. Akad. sci. Ukrajina, sv. 21.pp. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho a D. Niso. O praktickém využití eliminace proměnných v problémech optimalizace omezení: „Zátiší“ jako případová studie  //  Journal of Artificial Intelligence Research : deník. - 2005. - Sv. 23 . - str. 421-440 . Archivováno z originálu 16. července 2011.
  26. ↑ Neil Yorke-Smith. Zátiší s maximální hustotou . Centrum umělé inteligence . Mezinárodní SRI. Získáno 11. srpna 2013. Archivováno z originálu 19. května 2013.
  27. ↑ Počet stabilních n-buněčných vzorů („zátiší“) v Conwayově hře o život
  28. ↑ Počet n-buněčných pseudo-zátiší v Conwayově hře o život
  29. ↑ Niemiec, Mark D. Life Still-Lifes . Archivováno z originálu 21. ledna 2013.

Externí odkazy

 Conwayova hra o život a další buněčné automaty
Konfigurační třídy
Konfigurace
Podmínky
Jiná kosmická loď na
dvourozměrné mřížce
Živý
jiný
Jednorozměrná kosmická loď
Software a algoritmy
  • Golly
  • Mirkova
  • hashlife
výzkumníci KA