Naturaleza muerta (configuración de un autómata celular)

La naturaleza muerta es una clase de configuraciones en Life, el modelo de Conway de un autómata celular .

Descripción

En la formulación más general, el concepto de "naturaleza muerta" significa lo mismo que "figura estable" - la configuración de "Vida" u otro autómata celular que no cambia en el proceso de evolución [nota 1] . En otras palabras, la naturaleza muerta es un oscilador de 1 [1] [2] [3] períodos .

Terminología: bodegones y pseudobodegones

Hay varios términos que tienen un significado cercano y que denotan configuraciones que no cambian en el proceso de evolución ( configuraciones que son sus propios padres ). Las diferencias entre ellos están relacionadas con la respuesta a las siguientes preguntas:

  1. ¿Se considera naturaleza muerta una configuración formada por dos bodegones independientes (por ejemplo, dos bloques a una distancia suficientemente grande entre sí)? [cuatro]
  2. ¿Es una naturaleza muerta una configuración que consta de dos partes, cualquiera de las cuales se puede quitar para que la segunda parte siga siendo la madre de sí misma?

Los diccionarios y enciclopedias en línea existentes [3] [5] [6] [7] proporcionan las siguientes definiciones:

La definición exacta de "estabilidad" es de interés en el contexto de enumerar naturalezas muertas: por ejemplo, según las definiciones dadas, el número de configuraciones estables de tamaño 8 (es decir, que consta de 8 celdas vivas) en "Life" es infinito. , ya que un par de bloques a cualquier distancia entre sí es sostenible; sin embargo, el número de bodegones de tamaño limitado se considera finito [5] [6] [7] .

Pseudobodegón en "Life". Quitar una de las islas no afecta la estabilidad de la segunda isla.
Naturaleza muerta "estricta". La estabilidad de cada una de las islas depende de la disponibilidad de la otra isla.

Se conoce el número de bodegones y pseudobodegones no mayores de 24 celdas [7] [10] [11] .

El problema de determinar el tipo de configuración estable (naturaleza muerta, pseudo-naturaleza muerta) se resuelve en tiempo polinomial buscando ciclos en un gráfico sesgado simétrico conectado [12] .

Bodegones en "Vida"

En "Life" hay muchos bodegones naturales [13] .

Ejemplos simples

Bloque

La naturaleza muerta más común es un bloque [14] [15] [16] : una configuración en forma de cuadrado de 2 × 2. Dos bloques colocados en un rectángulo de 2 × 5 forman un bibloque : el pseudo-todavía más simple vida. Los bloques se utilizan como bloques de construcción en una variedad de dispositivos complejos, como la pistola planeadora Gosper [16] .

Colmena

La segunda naturaleza muerta más común es una colmena ( ing.  colmena, colmena ). Las colmenas a menudo aparecen en grupos de cuatro en una configuración llamada colmenar ( granja de miel en inglés  ) [14] [15] [16] .

Pan

El tercer bodegón más común es un pan ( ing.  pan ). Los panes aparecen a menudo en pares ( inglés  bi-loaf ) [14] [15] [16] . A su vez, los panes dobles también aparecen por parejas llamados panaderías ( del inglés  bakery ) [17] .

Cajas, barcazas, botes, barcos

La caja ( ing.  tub ) consta de cuatro células vivas en la vecindad de von Neumann de la célula muerta central. Agregar una celda viva en diagonal a la celda central convierte la caja en un bote ( barco inglés  ), y agregar otra celda simétricamente la convierte en un barco ( barco inglés ) [18] . El alargamiento natural de estas tres configuraciones da como resultado una barcaza ( barcaza inglesa ), un barco largo ( barcaza inglesa ) y un barco largo ( barcaza inglesa ) respectivamente. El alargamiento se puede continuar indefinidamente [5] [6] [15] [16] .     

De dos barcos puedes hacer otra naturaleza muerta: una proa de barco ( corbata de barco inglesa  ), y de dos barcos: la proa de un barco ( corbata de barco inglesa ) [5] [6] .  

Otros bodegones

  • Canoa

  • Portaaviones

  • Signo integral

  • Mango / Cigarro

  • Estanque

  • Serpiente

Devoradores y Reflectores

Los bodegones se pueden utilizar para modificar o destruir otros objetos. The Eater puede destruir la nave espacial y recuperarse de la reacción. El reflector ( en inglés reflector ) en lugar de destruir la nave espacial cambia la dirección de su vuelo.   

Reflectores y Devoradores no tienen por qué ser naturalezas muertas.

  • Comedores

  • Anzuelo / Comedor-1

  • Devorador-2

Densidad Máxima

El problema de colocar una naturaleza muerta con el máximo número de celdas en un área n  ×  n ha llamado la atención de los programadores como un problema de programación de restricciones [19] [20] [21] [22] [23] . Como el tamaño de la región tiende al infinito, no más del 50% de las células pueden estar vivas [24] . En áreas cuadradas finitas, se pueden lograr densidades más altas. Así, la densidad máxima de una naturaleza muerta en un cuadrado de 8 × 8 es 36/64 = 0,5625 - esta densidad la proporciona una muestra que consta de nueve bloques [19] Para cuadrados de hasta 20 × 20, se conocen soluciones óptimas [25 ] [26] .

  • Bodegones de máxima densidad en "Life"

  • 19x19

  • 20x20

Número de naturalezas muertas

Se conoce el número de bodegones y pseudobodegones de "Vida" hasta un tamaño de 24 celdas [27] [28] [29] .

Número de células vivas número de bodegones Ejemplos
una 0
2 0
3 0
cuatro 2 bloque, caja
5 una barco
6 5 barcaza, portaaviones, colmena, barco, serpiente
7 cuatro anzuelo, pan, bote largo
ocho 9 canoa, mango, barcaza larga, estanque
9 diez signo integral
diez 25 proa del barco
once 46
12 121 proa del barco
13 240
catorce 619 pan doble
quince 1353
dieciséis 3286
17 7773
Dieciocho 19044
19 45759 comedor 2
veinte 112243
21 273188
22 672172
23 1646147
24 4051711

Notas al pie

  1. ↑ Para definiciones más rigurosas, consulte Terminología.

Notas

  1. ↑ 1 2 Continuo . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 10 de febrero de 2013.
  2. ↑ 1 2 Estable (enlace descendente) . léxico de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 20 de febrero de 2009. 
  3. ↑ 1 2Eric Weisstein. naturaleza muerta Tesoro de la vida CA. Recuperado: 11 de agosto de 2013.  (enlace no disponible)
  4. ↑ Si la respuesta a esta pregunta es sí, entonces el número de bodegones con un número limitado de celdas es infinito.
  5. ↑ 1 2 3 4 Nikolái Belyuchenko. Diccionario de la vida . Archivado desde el original el 10 de octubre de 2012.
  6. ↑ 1 2 3 4 Stephen A. Plata. Léxico de  la vida . Archivado desde el original el 26 de mayo de 2013.
  7. ↑ 1 2 3 4 5 Naturaleza muerta . conwaylife.com. Consultado el 11 de agosto de 2013. Archivado desde el original el 30 de julio de 2013.
  8. ↑ Naturaleza muerta . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 10 de febrero de 2013.
  9. ↑ Bodegón (enlace no disponible) . léxico de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 20 de febrero de 2009. 
  10. ↑ 1 2 Pseudo-naturaleza muerta . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 6 de mayo de 2019.
  11. ↑ 1 2 Pseudo bodegón (enlace no disponible) . léxico de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 3 de diciembre de 2014. 
  12. ↑ Cook, Mateo (2003). "Teoría de la naturaleza muerta". Nuevas Construcciones en Autómatas Celulares . Estudios del Instituto Santa Fe en Ciencias de la Complejidad, Oxford University Press. páginas. 93-118.
  13. ↑ Una muestra natural es un objeto que aparece con relativa frecuencia en el proceso de desarrollo de una configuración aleatoria.
  14. ↑ 1 2 3 Achim Flammenkamp. Top 100 de Objetos Ash de Game-of-Life . Consultado el 5 de noviembre de 2008. Archivado desde el original el 22 de octubre de 2008.
  15. ↑ 1 2 3 4 El juego de la vida (revisión de Gardner) . Consultado el 11 de agosto de 2013. Archivado desde el original el 18 de octubre de 2012.
  16. ↑ 1 2 3 4 5 Klumova I. N. Juego "Life"  // Kvant . - 1974. - Nº 9 . - S. 26-30 .
  17. ↑ Panadería . Diccionario de la vida. Consultado el 11 de agosto de 2013. Archivado desde el original el 6 de mayo de 2019.
  18. ↑ No debe confundirse con nave espacial .
  19. ↑ 1 2 Bosch, RA Programación entera y el juego de la vida de Conway  (indefinido)  // SIAM Review. - 1999. - T. 41 , N º 3 . - S. 594-604 . -doi : 10.1137/ S0036144598338252 . .
  20. ↑ Bosch, RA Patrones estables de densidad máxima en variantes del juego de la vida de Conway  // Cartas de investigación de  operaciones : diario. - 2000. - vol. 27 , núm. 1 . - Pág. 7-11 . -doi : 10.1016 / S0167-6377(00)00016-X . .
  21. ^ Smith, Barbara M. Principios y práctica de la programación de restricciones - CP 2002   : revista . - Springer-Verlag, 2002. - vol. 2470 . - P. 89-94 . -doi : 10.1007/ 3-540-46135-3_27 . .
  22. ↑ Bosch, Roberto; Truco, Miguel. Programación de restricciones y formulaciones híbridas para tres diseños de Life  //  Annals of Operations Research : diario. - 2004. - vol. 130 , núm. 1-4 . - P. 41-56 . -doi : 10.1023/B : ANOR.0000032569.86938.2f . .
  23. ↑ Cheng, Kenil CK; Yap, Roland HC Aplicación de restricciones globales ad-hoc con la restricción de caso a la naturaleza muerta  //  Restricciones: diario. - 2006. - vol. 11 , núm. 2-3 . - P. 91-114 . -doi : 10.1007/ s10601-006-8058-9 . .
  24. ↑ Elkies, Noam D. (1998). “El problema de la densidad de la naturaleza muerta y sus generalizaciones”. El impacto de Voronoi en la ciencia moderna, Libro I. proc. Inst. Matemáticas. Nat. Academia ciencia Ucrania, vol. 21.pp. 228-253. arXiv : matemáticas.CO/ 9905194 .
  25. ↑ J. Larrosa, E. Morancho y D. Niso. Sobre el uso práctico de la eliminación de variables en problemas de optimización de restricciones: 'Naturaleza muerta' como estudio de caso  //  Journal of Artificial Intelligence Research : diario. - 2005. - vol. 23 . - P. 421-440 . Archivado desde el original el 16 de julio de 2011.
  26. ↑ Neil Yorke-Smith. Bodegón de máxima densidad . Centro de Inteligencia Artificial . SRI Internacional. Consultado el 11 de agosto de 2013. Archivado desde el original el 19 de mayo de 2013.
  27. ↑ Número de patrones estables de n celdas ("bodegones") en el juego de la vida de Conway
  28. ↑ Número de pseudo bodegones de n celdas en el juego de la vida de Conway
  29. ↑ Niemiec, Mark D. Vida Bodegones . Archivado desde el original el 21 de enero de 2013.

Enlaces externos

 El juego de la vida de Conway y otros autómatas celulares
Clases de configuración
Configuraciones
Términos
Otras naves espaciales en una
red bidimensional
Natural
Otro
Nave espacial unidimensional
Software y algoritmos
  • Caramba
  • Celebración de
  • hashlife
investigadores de ka