Csendélet (celluláris automata konfigurációja)

A csendélet a konfigurációk egy osztálya a Life-ban, amely Conway sejtautomata modellje .

Leírás

A legáltalánosabb megfogalmazásban a "csendélet" fogalma ugyanazt jelenti, mint a "stabil alak" - az "Élet" vagy egy másik sejtautomata konfigurációja, amely nem változik az evolúció folyamatában [nb 1] . Más szóval, a csendélet egy 1 [1] [2] [3] periódusú oszcillátor .

Terminológia: csendéletek és pszeudo-csendéletek

Számos olyan kifejezés van, amelyek jelentésükben közel állnak egymáshoz, és olyan konfigurációkat jelölnek, amelyek nem változnak az evolúció folyamatában (a konfigurációk, amelyek a saját szüleik ). A köztük lévő különbségek a következő kérdésekre adott válaszokhoz kapcsolódnak:

  1. Csendéletnek minősül- e az a konfiguráció, amely két független csendéletből áll (például két, egymástól kellően nagy távolságra lévő blokkból )? [négy]
  2. A csendélet két részből álló konfiguráció, amelyek közül bármelyik eltávolítható, így a második rész saját szülője marad?

A meglévő szótárak és online enciklopédiák [3] [5] [6] [7] a következő meghatározásokat adják:

A "stabilitás" pontos meghatározása a csendéletek felsorolása kapcsán érdekes: például a megadott definíciók szerint az "Élet"-ben végtelen a 8-as méretű (azaz 8 élő sejtből álló) stabil konfigurációk száma. , mivel az egymástól tetszőleges távolságban lévő blokkpárok stabilak ; a korlátozott méretű csendéletek számát azonban végesnek tekintjük [5] [6] [7] .

Álcsendélet az "Életben". Az egyik sziget eltávolítása nem befolyásolja a második sziget stabilitását.
"Szigorú" csendélet. Az egyes szigetek stabilitása a másik sziget elérhetőségétől függ.

A 24 cellánál nem nagyobb csendéletek és álcsendéletek száma ismert [7] [10] [11] .

A stabil konfiguráció típusának (csendélet, pszeudo-csendélet) meghatározásának problémáját polinomiális időben úgy oldjuk meg , hogy ciklusokat keresünk egy összefüggő ferde-szimmetrikus gráfban [12] .

Csendéletek az "Életben"

Az "Élet" -ben sok természetes [13] csendélet található.

Egyszerű példák

Blokkolás

A legelterjedtebb csendélet a blokk [14] [15] [16] - egy 2 × 2-es négyzet alakú konfiguráció Két 2 × 5 -ös téglalapban elhelyezett blokk egy biblokkot alkot - a legegyszerűbb pszeudo állókép élet. A blokkokat számos összetett eszköz építőelemeként használják, mint például a Gosper vitorlázó pisztolyban [16] .

Hive

A második leggyakoribb csendélet a méhkas ( eng.  hive, beehive ). A csalánkiütések gyakran négyesével jelennek meg a méhészet nevű konfigurációban ( angol  mézfarm ) [14] [15] [16] .

Vekni

A harmadik leggyakoribb csendélet a cipó ( angol  loaf ). A kenyerek gyakran párban jelennek meg ( angolul  bi-loaf ) [14] [15] [16] . Viszont a dupla cipók is megjelennek párokban, amelyeket pékségeknek neveznek ( angol  bakery ) [17] .

Ládák, bárkák, csónakok, hajók

A doboz ( eng.  tub ) négy élő sejtből áll a központi elhalt sejt von Neumann szomszédságában . Ha egy élő sejtet átlósan a központi cellához adunk, akkor a doboz csónakká alakul (angol boat ) , egy másik sejt szimmetrikus hozzáadása pedig hajóvá ( angol hajó ) [18] . E három konfiguráció természetes megnyúlása egy uszályt ( angol barge ), egy hosszú csónakot ( angol long-boat ) és egy hosszú hajót ( angol long-ship ) ad. A hosszabbítás korlátlanul folytatható [5] [6] [15] [16] .      

Két csónakból egy másik csendéletet - csónakíj ( angol  boat tie ), két hajóból pedig - hajóorr ( angol  ship tie ) készíthet [5] [6] .

Egyéb csendéletek

  • Kenu

  • Repülőgép hordozó

  • Integrált jel

  • Mangó / szivar

  • Tavacska

  • Kígyó

Devourers and Reflectors

A csendéletek felhasználhatók más tárgyak módosítására vagy megsemmisítésére. Az Eater képes elpusztítani az űrhajót és felépülni a reakcióból. A reflektor ( angol reflektor ) ahelyett, hogy megsemmisítené az űreszközt, megváltoztatja repülési irányát.   

A fényvisszaverőknek és a zabálóknak nem kell csendéleteknek lenniük.

  • Evők

  • Fishhook / Eater-1

  • Devourer-2

Maximális sűrűség

A maximális számú cellaszámú csendélet n  ×  n területen való elhelyezésének problémája kényszerprogramozási problémaként hívta fel a programozók figyelmét [19] [20] [21] [22] [23] . Mivel a régió mérete a végtelenbe hajlik, a sejtek legfeljebb 50%-a lehet életben [24] . A véges négyzetes területeken nagyobb sűrűség érhető el. Így a csendélet maximális sűrűsége egy 8 × 8-as négyzetben 36/64 = 0,5625 – ezt a sűrűséget egy kilenc blokkból álló minta adja [19] A 20 × 20-ig terjedő négyzetekre az optimális megoldások ismertek [25] ] [26] .

  • Maximális sűrűségű csendéletek az Életben

  • 19x19

  • 20x20

Csendéletek száma

Az "Élet"-ben szereplő csendéletek és álcsendéletek száma 24 cella méretig ismert [27] [28] [29] .

Élő sejtek száma Csendéletek száma Példák
egy 0
2 0
3 0
négy 2 blokk, doboz
5 egy hajó
6 5 uszály, repülőgép-hordozó, méhkas, hajó, kígyó
7 négy horgászhorog, cipó, hosszú csónak
nyolc 9 kenu, mangó, hosszú bárka, tó
9 tíz integrál jel
tíz 25 csónak orr
tizenegy 46
12 121 hajóorr
13 240
tizennégy 619 dupla cipó
tizenöt 1353
16 3286
17 7773
tizennyolc 19044
19 45759 evő 2
húsz 112243
21 273188
22 672172
23 1646147
24 4051711

Lábjegyzetek

  1. ↑ A szigorúbb definíciókért lásd: Terminológia.

Jegyzetek

  1. ↑ 1 2 Állandó . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2013. február 10.
  2. ↑ 1 2 Stabil (lefelé irányuló kapcsolat) . életlexikon. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2009. február 20.. 
  3. ↑ 1 2 Eric Weisstein. csendélet . Treasure Trove of Life CA. Letöltve: 2013. augusztus 11.  (nem elérhető link)
  4. ↑ Ha erre a kérdésre igen a válasz, akkor a korlátozott számú cellával rendelkező csendéletek száma végtelen.
  5. ↑ 1 2 3 4 Nyikolaj Beljucsenko. Életszótár . Az eredetiből archiválva: 2012. október 10.
  6. ↑ 1 2 3 4 Stephen A. Silver. Életlexikon  . _ Archiválva az eredetiből 2013. május 26-án.
  7. ↑ 1 2 3 4 5 Csendélet . conwaylife.com. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2013. július 30.
  8. ↑ Csendélet . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2013. február 10.
  9. ↑ Csendélet (nem elérhető link) . életlexikon. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2009. február 20.. 
  10. ↑ 1 2 Álcsendélet . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2019. május 6..
  11. ↑ 1 2 Álcsendélet (nem elérhető link) . életlexikon. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2014. december 3.. 
  12. ↑ Cook, Matthew (2003). "Csendélet elmélet". Új konstrukciók a cellás automatákban . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93-118.
  13. ↑ A természetes minta olyan objektum, amely viszonylag gyakran előfordul egy véletlenszerű konfiguráció kialakítása során.
  14. ↑ 1 2 3 Achim Flammenkamp. A Game-of-Life Ash Objects 100 legjobbja . Letöltve: 2008. november 5. Az eredetiből archiválva : 2008. október 22..
  15. ↑ 1 2 3 4 Az élet játéka (Gardner ismertető) . Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2012. október 18..
  16. ↑ 1 2 3 4 5 Klumova I. N. Játék "Élet"  // Kvant . - 1974. - 9. sz . - S. 26-30 .
  17. ↑ Pékség . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2019. május 6..
  18. ↑ Nem tévesztendő össze az űrhajókkal .
  19. ↑ 1 2 Bosch, RA Integer programozás és Conway életjátéka  (határozatlan)  // SIAM Review. - 1999. - T. 41 , 3. sz . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Maximális sűrűségű stabil minták Conway életjátékának változataiban  //  Operations Research Letters : folyóirat. - 2000. - Vol. 27 , sz. 1 . - 7-11 . o . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ↑ Smith, Barbara M. A kényszerprogramozás alapelvei és gyakorlata - CP 2002   : folyóirat . - Springer-Verlag, 2002. - Vol. 2470 . - 89-94 . o . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Trükk, Michael. Kényszerprogramozás és hibrid megfogalmazások három élettervhez  //  Annals of Operations Research : folyóirat. - 2004. - 20. évf. 130 , sz. 1-4 . - 41-56 . o . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Ad-hoc globális megszorítások alkalmazása az eset-megszorítással csendéletekre  //  Constraints : Journal. - 2006. - Vol. 11 , sz. 2-3 . - 91-114 . o . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). „A csendélet sűrűségproblémája és általánosításai”. Voronoi hatása a modern tudományra, I. könyv. Proc. Inst. Math. Nat. Acad. sci. Ukrajna, vol. 21.pp. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho és D. Niso. A változó kiküszöbölés gyakorlati felhasználásáról a kényszeroptimalizálási problémákban: „Csendélet” esettanulmányként  //  Journal of Artificial Intelligence Research : folyóirat. - 2005. - 20. évf. 23 . - P. 421-440 . Archiválva az eredetiből 2011. július 16-án.
  26. ↑ Neil Yorke-Smith. Maximális sűrűségű csendélet . Mesterséges Intelligencia Központ . SRI International. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2013. május 19.
  27. ↑ Stabil n-cellás minták ("csendéletek") száma Conway Life játékában
  28. ↑ n-sejtű álcsendéletek száma Conway Life játékában
  29. ↑ Niemiec, Mark D. Életcsendéletek . Archiválva az eredetiből 2013. január 21-én.

Külső linkek

 Conway Game of Life és más sejtautomaták
Konfigurációs osztályok
Konfigurációk
Feltételek
Más űrhajók
kétdimenziós rácson
Élethű
Egyéb
Egydimenziós űrhajó
Szoftverek és algoritmusok
  • Golly_
  • ünnepe
  • hashlife
KA kutatók