Natura moartă (configurarea unui automat celular)

Natura moartă este o clasă de configurații în Life, modelul lui Conway al unui automat celular .

Descriere

În formularea cea mai generală, conceptul de „natura moartă” înseamnă la fel ca „figura stabilă” - configurația „Vieții” sau alt automat celular care nu se schimbă în procesul de evoluție [nb 1] . Cu alte cuvinte, natura moartă este un oscilator cu 1 [1] [2] [3] perioade .

Terminologie: natură moartă și pseudo-natură moartă

Există mai mulți termeni care sunt apropiați ca înțeles, denotă configurații care nu se schimbă în procesul de evoluție ( configurații care sunt proprii părinți ). Diferențele dintre ele sunt legate de răspunsul la următoarele întrebări:

  1. O configurație care constă din două naturi moarte independente (de exemplu, două blocuri aflate la o distanță suficient de mare unul de celălalt) este considerată a fi o natură moartă? [patru]
  2. Este o natură moartă o configurație formată din două părți, oricare dintre acestea putând fi îndepărtată, astfel încât a doua parte să rămână părintele în sine?

Dicționarele și enciclopediile online existente [3] [5] [6] [7] oferă următoarele definiții:

Definiția exactă a „stabilității” este de interes în contextul enumerarii naturilor moarte: de exemplu, conform definițiilor date, numărul de configurații stabile de dimensiunea 8 (adică, constând din 8 celule vii) din „Viața” este infinit. , deoarece o pereche de blocuri la orice distanță unul de celălalt este durabilă; cu toate acestea, numărul de naturi moarte de dimensiune limitată este considerat finit [5] [6] [7] .

Pseudo-natura moartă în „Viață”. Îndepărtarea uneia dintre insule nu afectează stabilitatea celei de-a doua insule.
Natura moartă „strict”. Stabilitatea fiecăreia dintre insule depinde de disponibilitatea celeilalte insule.

Numărul de naturi moarte și pseudo-naturi moarte nu mai mare de 24 de celule este cunoscut [7] [10] [11] .

Problema determinării tipului de configurație stabilă (natura moartă, pseudo-natura moartă) se rezolvă în timp polinomial prin căutarea ciclurilor într-un grafic skew-simetric conex [12] .

Naturi moarte în „Viața”

În „Viața” există multe naturi [13] naturale.

Exemple simple

Blocare

Cea mai comună natură moartă este un bloc [14] [15] [16] - o configurație sub forma unui pătrat de 2 × 2. Două blocuri plasate într-un dreptunghi de 2 × 5 formează un bi-bloc - cel mai simplu pseudo-still viaţă. Blocurile sunt folosite ca blocuri de construcție într-o varietate de dispozitive complexe, cum ar fi pistolul de planor Gosper [16] .

Stup

A doua cea mai frecventă natură moartă este un stup ( ing.  stup, stup ). Stupii apar adesea în patru patru într-o configurație numită stupină ( fermă engleză  de miere ) [14] [15] [16] .

Pâine

A treia cea mai frecventă natură moartă este o pâine ( ing.  pâine ). Pâinile apar adesea în perechi ( engleză  bi-loaf ) [14] [15] [16] . La rândul lor, pâinile duble apar și în perechi numite brutării ( English  bakery ) [17] .

Lăzi, șlepuri, bărci, nave

Cutia ( ing.  tub ) constă din patru celule vii în cartierul von Neumann al celulei moarte centrale. Adăugarea unei celule vii în diagonală la celula centrală transformă cutia într- o barcă ( barcă engleză  ), iar adăugarea unei alte celule o transformă simetric într- o navă ( navă engleză ) [18] . Alungirea naturală a acestor trei configurații dă o șlep ( English barge ), o barcă lungă ( English long-boat ) și respectiv o navă lungă ( English long-ship ). Prelungirea poate fi continuată la nesfârșit [5] [6] [15] [16] .     

Din două bărci puteți face o altă natură moartă - o arc de barca ( English  boat tie ), iar din două nave - a ship's bow ( English  ship tie ) [5] [6] .

Alte naturi moarte

  • Canoe

  • Portavion

  • Semn integral

  • Mango / Trabuc

  • Iaz

  • Şarpe

Devoratoare și reflectoare

Naturile moarte pot fi folosite pentru a modifica sau distruge alte obiecte. Eater este capabil să distrugă nava spațială și  să se recupereze din reacție. Reflectorul ( reflector în engleză ) în loc să distrugă nava spațială își schimbă direcția zborului.  

Reflectoarele și Devoratoarele nu trebuie să fie neapărat natură moartă.

  • Mâncătorii

  • Cârlig / Mâncător-1

  • Devorator-2

Densitatea maximă

Problema plasării unei naturi moarte cu numărul maxim de celule într- o zonă n  ×  n a atras atenția programatorilor ca problemă de programare cu constrângeri [19] [20] [21] [22] [23] . Deoarece dimensiunea regiunii tinde spre infinit, nu mai mult de 50% din celule pot fi vii [24] . În zonele pătrate finite, se pot obține densități mai mari. Astfel, densitatea maximă a unei naturi moarte într-un pătrat de 8 × 8 este 36/64 = 0,5625 - această densitate este furnizată de un eșantion format din nouă blocuri [19] Pentru pătratele de până la 20 × 20 se cunosc soluții optime [25] ] [26] .

  • Naturi moarte de densitate maximă în „Life”

  • 19x19

  • 20x20

Numărul de naturi moarte

Numărul de naturi moarte și pseudo-naturi moarte din „Life” este cunoscut până la o dimensiune de 24 de celule [27] [28] [29] .

Numărul de celule vii Numărul de naturi moarte Exemple
unu 0
2 0
3 0
patru 2 bloc, cutie
5 unu barcă
6 5 șlep, portavion, stup, corabie, șarpe
7 patru cârlig de pescuit, pâine, barcă lungă
opt 9 canoe, mango, barjă lungă, iaz
9 zece semn integral
zece 25 prova barca
unsprezece 46
12 121 prova navei
13 240
paisprezece 619 pâine dublă
cincisprezece 1353
16 3286
17 7773
optsprezece 19044
19 45759 mâncător 2
douăzeci 112243
21 273188
22 672172
23 1646147
24 4051711

Note de subsol

  1. ↑ Pentru definiții mai riguroase, vezi Terminologie.

Note

  1. ↑ 1 2 Stabil . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 10 februarie 2013.
  2. ↑ 1 2 Stabil (link descendent) . lexicon de viață. Preluat la 11 august 2013. Arhivat din original la 20 februarie 2009. 
  3. ↑ 1 2 Eric Weisstein. natură moartă . Treasure Trove of Life CA. Preluat: 11 august 2013.  (link indisponibil)
  4. ↑ Dacă răspunsul la această întrebare este da, atunci numărul de naturi moarte cu un număr limitat de celule este infinit.
  5. ↑ 1 2 3 4 Nikolai Beliucenko. Dicţionar al vieţii . Arhivat din original pe 10 octombrie 2012.
  6. ↑ 1 2 3 4 Stephen A. Silver. Lexicon de  viață . Arhivat din original pe 26 mai 2013.
  7. ↑ 1 2 3 4 5 Natura moartă . conwaylife.com. Preluat la 11 august 2013. Arhivat din original la 30 iulie 2013.
  8. ↑ Natura moartă . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 10 februarie 2013.
  9. ↑ Natura moartă (link indisponibil) . lexicon de viață. Preluat la 11 august 2013. Arhivat din original la 20 februarie 2009. 
  10. ↑ 1 2 Pseudo-natură moartă . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 6 mai 2019.
  11. ↑ 1 2 Pseudo natură moartă (link indisponibil) . lexicon de viață. Preluat la 11 august 2013. Arhivat din original la 3 decembrie 2014. 
  12. ↑ Cook, Matthew (2003). „Teoria naturii moarte”. Construcții noi în automate celulare . Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93-118.
  13. ↑ O probă naturală este un obiect care apare relativ des în procesul de dezvoltare a unei configurații aleatorii.
  14. ↑ 1 2 3 Achim Flammenkamp. Top 100 al obiectelor din frasin din Game-of-Life . Consultat la 5 noiembrie 2008. Arhivat din original pe 22 octombrie 2008.
  15. ↑ 1 2 3 4 Jocul vieții (recenzia Gardner) . Preluat la 11 august 2013. Arhivat din original la 18 octombrie 2012.
  16. ↑ 1 2 3 4 5 Klumova I. N. Jocul „Viața”  // Kvant . - 1974. - Nr 9 . - S. 26-30 .
  17. ↑ Brutărie . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 6 mai 2019.
  18. ↑ A nu se confunda cu navele spațiale .
  19. ↑ 1 2 Bosch, RA Integer programare și Conway’s Game of Life  (nedefinită)  // SIAM Review. - 1999. - T. 41 , nr 3 . - S. 594-604 . - doi : 10.1137/S0036144598338252 . .
  20. ↑ Bosch, RA Modele stabile de densitate maximă în variante ale jocului Life al lui Conway  // Scrisori de cercetare  operațională : jurnal. - 2000. - Vol. 27 , nr. 1 . - P. 7-11 . - doi : 10.1016/S0167-6377(00)00016-X . .
  21. ^ Smith, Barbara M. Principles and Practice of Constraint Programming - CP 2002   : jurnal . - Springer-Verlag, 2002. - Vol. 2470 . - P. 89-94 . - doi : 10.1007/3-540-46135-3_27 . .
  22. ↑ Bosch, Robert; Truc, Michael. Programare de constrângeri și formulări hibride pentru trei modele Life  //  Analele cercetării operaționale : jurnal. - 2004. - Vol. 130 , nr. 1-4 . - P. 41-56 . - doi : 10.1023/B:ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil C.K.; Yap, Roland HC Aplicarea constrângerilor globale ad-hoc cu constrângerea caz la natura moartă  //  Constrângeri : jurnal. - 2006. - Vol. 11 , nr. 2-3 . - P. 91-114 . - doi : 10.1007/s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). „Problema densității naturii moarte și generalizările ei”. Impactul lui Voronoi asupra științei moderne, cartea I. Proc. Inst. Matematică. Nat. Acad. sci. Ucraina, vol. 21.pp. 228-253. arXiv : math.CO/9905194 .
  25. ↑ J. Larrosa, E. Morancho și D. Niso. Despre utilizarea practică a eliminării variabilelor în problemele de optimizare a constrângerilor: „Natura moartă” ca studiu de caz  //  Journal of Artificial Intelligence Research : jurnal. - 2005. - Vol. 23 . - P. 421-440 . Arhivat din original pe 16 iulie 2011.
  26. ↑ Neil Yorke-Smith. Natura statică cu densitate maximă . Centrul de Inteligență Artificială . SRI International. Preluat la 11 august 2013. Arhivat din original la 19 mai 2013.
  27. ↑ Numărul de modele n-celulare stabile („natură moartă”) în jocul Life al lui Conway
  28. ↑ Numărul de pseudo-naturi moarte cu n celule din jocul Life al lui Conway
  29. ↑ Niemiec, Mark D. Life Still-Lifes . Arhivat din original pe 21 ianuarie 2013.

Link- uri externe

 Conway’s Game of Life și alte automate celulare
Clasele de configurare
Configurații
Termeni
O altă navă spațială pe o
rețea bidimensională
Realistic
Alte
Nave spațiale unidimensionale
Software și algoritmi
  • Golly
  • Celebrarea lui
  • hashlife
Cercetătorii KA