En El juego de la vida 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 puede considerarse como un oscilador con un período unitario. [1]
Una pseudo naturaleza muerta consiste en dos o más islas adyacentes ( componentes conectados ) que pueden dividirse (ya sea 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 solo una isla, o puede tener múltiples islas que dependen unas de otras para su estabilidad y, por lo tanto, no pueden descomponerse. La distinción entre los dos no siempre es obvia, ya que una naturaleza muerta estricta 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 buscando ciclos en un gráfico antisimétrico asociado . [2]
En El juego de la vida de Conway aparecen muchas naturalezas muertas de forma natural . 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 tiene más probabilidades de generarse a partir de un estado inicial aleatorio) es la de bloques . [3] Un par de bloques colocados uno al lado del otro (o bibloque ) es la pseudonaturaleza muerta más simple. Los bloques se utilizan como componentes en muchos dispositivos complejos, un ejemplo es el cañón planeador Gosper .
La segunda naturaleza muerta más común es la colmena (o colmena ). [3] Las colmenas se crean con frecuencia en grupos de cuatro (sin interacción), en una formación conocida como granja de miel .
El tercer bodegón más común es el pan de molde . [3] Los panes se suelen encontrar juntos en una pareja conocida como bipan . Los bipanes a su vez suelen crearse en otra pareja (sin interacción) conocida como panadería . Es extremadamente raro que se formen dos panaderías una al lado de la otra, formando un conjunto de cuatro panes conocido como tetrapan junto a dos bipanes más.
Una tina consta de cuatro celdas vivas colocadas en forma de diamante alrededor de una celda muerta central. Colocando una celda viva adicional en diagonal a la celda central se obtiene otra naturaleza muerta, conocida como barco . Colocando otra celda viva en el lado opuesto se obtiene otra naturaleza muerta, conocida como barco . Una tina, un barco o un barco se pueden ampliar añadiendo un par de celdas vivas, para dar una barcaza , un barco largo o un barco largo respectivamente. Esta extensión se puede repetir indefinidamente, para dar estructuras arbitrariamente grandes.
Un par de barcos se pueden combinar para dar lugar a otra naturaleza muerta conocida como corbata de barco (un juego de palabras con pajarita , a la que superficialmente se parece). De manera similar, un par de barcos se pueden combinar para formar una corbata de barco .
Los bodegones se pueden utilizar para modificar o destruir otros objetos. Un bodegón se llama devorador cuando se puede utilizar para absorber algún otro patrón (a menudo un planeador , una nave espacial o los restos 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 devorador 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 llamarse devoradores o reflectores, pero son más difíciles de aplicar ya que deben estar sincronizados con el patrón que modifican. Los devoradores y reflectores de bodegones, por otro lado, funcionan correctamente independientemente del momento del patrón que modifican, siempre que las reacciones sucesivas ocurran con suficiente separación en el tiempo para permitir que el devorador o el reflector recuperen su forma original.
El número de naturalezas muertas estrictas y pseudonaturales 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 Enteras (OEIS)). [4] [5]
El problema de ajustar una región n×n con un bodegón de máxima densidad ha atraído la atención como un caso de prueba para la programación de restricciones . [9] [10] [11] [12] [13] En el límite de una cuadrícula infinitamente grande, no más de la mitad de las celdas en el plano pueden estar vivas. [14] Para cuadrículas cuadradas finitas, se pueden lograr mayores densidades. Por ejemplo, el bodegón de máxima densidad dentro de un cuadrado de 8×8 es una cuadrícula regular de nueve bloques, con una densidad de 36/64 = 0,5625. [9] Se conocen soluciones óptimas para cuadrados de todos los tamaños. [15] Yorke-Smith proporciona una lista de patrones de máxima densidad finita conocidos. [16]