En Game of Life de Conway y otros autómatas celulares , una naturaleza muerta es un patrón que no cambia de una generación a la siguiente. El término proviene del mundo del arte, donde una pintura o fotografía de naturaleza muerta representa una escena inanimada. En los autómatas celulares, una naturaleza muerta se puede considerar como un oscilador con un período de unidad. [1]
Clasificación
Una pseudo naturaleza muerta consta de dos o más islas adyacentes ( componentes conectados ) que se pueden dividir (individualmente o como conjuntos) en subpartes que no interactúan, que también son naturalezas muertas. Esto se compara con una naturaleza muerta estricta , que no puede dividirse de esta manera. Una naturaleza muerta estricta puede tener una sola isla, o puede tener varias islas que dependen unas de otras para la estabilidad y, por lo tanto, no se pueden descomponer. La distinción entre los dos no siempre es obvia, ya que un bodegón estricto puede tener múltiples componentes conectados, todos los cuales son necesarios para su estabilidad. Sin embargo, es posible determinar si un patrón de naturaleza muerta es una naturaleza muerta estricta o una pseudo naturaleza muerta en tiempo polinomial mediante la búsqueda de ciclos en un gráfico simétrico sesgado asociado . [2]
Ejemplos de
Hay muchas naturalezas muertas en el Juego de la vida de Conway . Un patrón inicial aleatorio dejará una gran cantidad de escombros, que contienen pequeños osciladores y una gran variedad de naturalezas muertas.
La naturaleza muerta más común (es decir, la que más probablemente se genere a partir de un estado inicial aleatorio) es el bloque . [3] Un par de bloques colocados uno al lado del otro (o bi-bloque ) es la pseudo naturaleza muerta más simple. Los bloques se utilizan como componentes en muchos dispositivos complejos, un ejemplo es el cañón planeador Gosper .
El segundo bodegón más común es la colmena (o colmena ). [3] Las colmenas se crean con frecuencia en conjuntos de cuatro (que no interactúan), en una formación conocida como granja de miel .
El tercer bodegón más común es el pan . [3] Los panes a menudo se encuentran juntos en un emparejamiento conocido como bi- panes . Los bipanes en sí mismos a menudo se crean en un emparejamiento adicional (que no interactúa) conocido como panadería . Rara vez se pueden formar dos panaderías una al lado de la otra, formando un conjunto de cuatro panes conocidos como tetraloaf junto con dos bi-panes más.
Una tina consta de cuatro células vivas colocadas en forma de diamante alrededor de una célula muerta central. Colocar una celda viva adicional en diagonal a la celda central da otra naturaleza muerta, conocida como bote . Colocar una celda viva más en el lado opuesto da otra naturaleza muerta, conocida como barco . Una tina, un bote o un barco se pueden ampliar agregando un par de células vivas, para dar una barcaza , un bote o un bote, respectivamente. Esta extensión puede repetirse indefinidamente, para dar estructuras arbitrariamente grandes.
Un par de botes se pueden combinar para dar otra naturaleza muerta conocida como corbata de bote (un juego de palabras con pajarita , a la que se parece superficialmente). Del mismo modo, un par de barcos se pueden combinar en una atadura de barco .
Comedores
Las naturalezas muertas se pueden utilizar para modificar o destruir otros objetos. Un bodegón se llama devorador cuando se puede usar para absorber algún otro patrón (a menudo un planeador , una nave espacial o los escombros de una reacción más complicada) y vuelve a su estado original después de la colisión. Existen muchos ejemplos, siendo el más notable el anzuelo (también conocido como eater 1 ), que es capaz de absorber varios tipos de naves espaciales. Un dispositivo similar es el " reflector ", que altera la dirección de una nave espacial entrante. Los osciladores con propiedades similares también pueden denominarse devoradores o reflectores, pero son más difíciles de aplicar ya que deben estar sincronizados con el patrón que modifican. Los bodegones y reflectores, por otro lado, funcionan correctamente independientemente de la sincronización del patrón que modifiquen, siempre que se produzcan reacciones sucesivas con suficiente separación en el tiempo para permitir que el devorador o reflector recupere su forma original.
Enumeración
El número de estrictas y pseudo naturalezas muertas en el Juego de la vida de Conway existentes para un número dado de células vivas se ha documentado hasta un valor de 34 (secuencias A019473 y A056613 respectivamente en la Enciclopedia en línea de secuencias de enteros (OEIS). [ 4] [5]
Células vivas | Estrictas naturalezas muertas | Pseudo bodegones | Ejemplos [1] |
---|---|---|---|
1 | 0 | 0 | |
2 | 0 | 0 | |
3 | 0 | 0 | |
4 | 2 | 0 | Bloque, tina |
5 | 1 | 0 | Bote |
6 | 5 | 0 | Barcaza, colmena, portador, barco, serpiente |
7 | 4 | 0 | Anzuelo, pan, bote, pitón |
8 | 9 | 1 | Canoa, mango, barcaza larga, estanque |
9 | 10 | 1 | Sombrero, signo integral |
10 | 25 | 7 | Bloque en la mesa, amarre para botes, lazo |
11 | 46 | dieciséis | |
12 | 121 | 55 | Ship-tie [ cita requerida ] |
13 | 240 | 110 | |
14 | 619 | 279 | Bi-loaf [ cita requerida ] |
15 | 1,353 | 620 | |
dieciséis | 3286 | 1,645 | |
17 | 7.773 | 4.067 | |
18 | 19,044 | 10,843 | |
19 | 45,759 | 27,250 | Devorador 2 [ cita requerida ] |
20 | 112,243 | 70,637 | |
21 | 273.188 | 179.011 | |
22 | 672,172 | 462,086 | |
23 | 1,646,147 | 1,184,882 | |
24 | 4.051.732 | 3,069,135 | |
25 | 9,971,377 | 7,906,676 | |
26 | 24,619,307 | 20,463,274 | |
27 | 60,823,008 | 52,816,265 | |
28 | 150,613,157 | 136,655,095 | |
29 | 373,188,952 | 353,198,379 | |
30 | 926,068,847 | 914,075,620 | |
31 | 2,299,616,637 | 2,364,815,358 | |
32 | 5.716.948.683 | 6.123.084.116 | |
33 | 14,223,867,298 | 15,851,861,075 | |
34 | 35,422,864,104 | 41,058,173,683 |
Densidad
El problema de ajustar una región n × n con una naturaleza muerta de máxima densidad ha atraído la atención como un caso de prueba para la programación de restricciones . [6] [7] [8] [9] [10] En el límite de una cuadrícula infinitamente grande, no más de la mitad de las celdas del plano pueden estar activas. [11] Para cuadrículas cuadradas finitas, se pueden lograr mayores densidades. Por ejemplo, la densidad máxima de naturaleza muerta dentro de un cuadrado de 8 × 8 es una cuadrícula regular de nueve bloques, con densidad 36/64 = 0,5625. [6] Se conocen soluciones óptimas para cuadrados de todos los tamaños. [12] Yorke-Smith proporciona una lista de patrones de densidad máxima finitos conocidos. [13]
Referencias
- ^ a b "Naturaleza muerta - del tesoro de la vida CA de Eric Weisstein" Consultado el 24 de enero de 2009 .
- ^ Cook, Matthew (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ágs. 93-118.
- ^ a b c Achim Flammenkamp. "Top 100 de objetos de ceniza de Game-of-Life" . Consultado el 5 de noviembre de 2008 .
- ^ Número de patrones de n-celdas estables ("naturalezas muertas") en el juego de la vida de Conway (secuencia A019473 en la OEIS ).
- ↑ Número de pseudo-naturalezas muertas n-celdas en el juego de la vida de Conway (secuencia A056613 en la OEIS ).
- ^ a b Bosch, RA (1999). "Programación entera y juego de la vida de Conway" . Revisión SIAM . 41 (3): 594–604. Código Bibliográfico : 1999SIAMR..41..594B . doi : 10.1137 / S0036144598338252 ..
- ^ Bosch, RA (2000). "Patrones estables de densidad máxima en variantes del juego de la vida de Conway". Cartas de investigación operativa . 27 (1): 7–11. doi : 10.1016 / S0167-6377 (00) 00016-X ..
- ^ Smith, Barbara M. (2002). "Una traducción de gráfico dual de un problema en 'Life ' ". Principios y práctica de la programación de restricciones - CP 2002 . Apuntes de conferencias en Ciencias de la Computación. 2470 . Springer-Verlag. págs. 89–94. doi : 10.1007 / 3-540-46135-3_27 ..
- ^ Bosch, Robert; Truco, Michael (2004). "Programación de restricciones y formulaciones híbridas para tres diseños Life". Anales de investigación operativa . 130 (1–4): 41–56. doi : 10.1023 / B: ANOR.0000032569.86938.2f ..
- ^ Cheng, Kenil CK; Yap, Roland HC (2006). "Aplicación de restricciones globales ad-hoc con la restricción de caso a naturaleza muerta". Restricciones . 11 (2-3): 91-114. doi : 10.1007 / s10601-006-8058-9 ..
- ^ Elkies, Noam D. (1998). "El problema de la densidad de la naturaleza muerta y sus generalizaciones". Impacto de Voronoi en la ciencia moderna, Libro I . Proc. Inst. Matemáticas. Nat. Acad. Sci. Ucrania, vol. 21. págs. 228-253. arXiv : math.CO/9905194 .
- ^ Chu, Geoffrey; Stuckey, Peter J. (1 de junio de 2012). "Una solución completa al problema de la naturaleza muerta de máxima densidad" . Inteligencia artificial . 184-185: 1-16. doi : 10.1016 / j.artint.2012.02.001 .
- ^ Neil Yorke-Smith. "Bodegón de máxima densidad" . Centro de Inteligencia Artificial . SRI Internacional .