La vida sin muerte es un autómata celular , similar al Juego de la vida de Conway y otrasreglas de autómatas celulares similares a la vida . En este autómata celular, un patrón de semilla inicial crece de acuerdo con la misma regla que en el Juego de la vida de Conway; sin embargo, a diferencia de Life, los patrones nunca se encogen. La regla fue considerada originalmente por Toffoli y Margolus (1987) , quienes la llamaron "Inkspot"; [1] también se le ha llamado "Flakes". [2] En contraste con los patrones más complejos que existen dentro del Juego de la vida de Conway, Vida sin muerte comúnmente presentapatrones de naturaleza muerta , en los que no ocurre ningún cambio, y escalera patrones, que crecen en línea recta.
Reglas
Un autómata celular es un tipo de modelo estudiado en matemáticas y biología teórica que consiste en una cuadrícula regular de celdas, cada una en uno de un número finito de estados, como "encendido" y "apagado". Un patrón en el autómata celular Vida sin Muerte consiste en una cuadrícula bidimensional infinita de células, cada una de las cuales puede estar en uno de dos estados: muerta o viva. De manera equivalente, se puede pensar en una matriz de píxeles , cada uno de los cuales puede ser blanco y negro; en las figuras, los píxeles blancos representan células vivas, mientras que los píxeles negros representan células muertas. Dos de estas celdas se consideran vecinas si son adyacentes vertical, horizontal o diagonalmente. [3]
Cualquier patrón de este tipo cambia a lo largo de una secuencia de pasos de tiempo aplicando las siguientes reglas simples simultáneamente a todas las celdas del patrón: cada celda que estaba viva en el patrón anterior permanece viva, cada celda muerta que tiene exactamente 3 vecinos vivos se vuelve viva ella misma, y todas las demás células muertas permanecen muertas. Es decir, en la notación que describe las reglas de autómatas celulares similares a la vida , es la regla B3 / S012345678: una célula viva nace cuando hay 3 vecinos vivos, y una célula viva sobrevive con cualquier número de vecinos.
Brotes y escaleras
Los patrones de naturaleza muerta son comunes en Vida sin muerte: si no hay una celda muerta con tres vecinos vivos, un patrón permanecerá inalterable para todos los pasos de tiempo futuros. Sin embargo, debido a que una célula, una vez viva, permanece viva, el conjunto de células vivas crece monótonamente a lo largo de la evolución de un patrón, y no puede haber osciladores (patrones que recorren una secuencia repetida de formas), naves espaciales (patrones que mantienen el patrón). misma forma pero cambia de posición), o los otros patrones más complejos que existen dentro del Juego de la vida de Conway.
En cambio, una característica común en los patrones de Vida sin muerte es la presencia de escaleras , patrones que crecen en línea recta. Una escalera crecerá para siempre a menos que se encuentre con alguna otra parte del patrón y se bloquee o a menos que algún patrón de crecimiento más rápido la supere. El patrón de escalera más común se muestra en la figura; cada doce pasos, la misma forma aparece en la punta de la escalera, cuatro celdas más lejos de la posición inicial de la escalera. [4] La velocidad de crecimiento de la escalera es, por lo tanto, cuatro celdas por doce pasos, o, en notación Life, 4 c / 12 = c / 3; aquí c representa una unidad de distancia por paso de tiempo. [5] Otro patrón común (llamado "brote parásito" por Gravner y Griffeath [4] ) avanza dos veces más rápido, a una velocidad de 2 c / 3, a lo largo del costado de una escalera, bloqueando finalmente la escalera y provocando una explosión caótica. [4] [6]
Dean Hickerson descubrió en 2000 escaleras variantes de otras velocidades, junto con algunos brotes parásitos que son más lentos que el más común de 2 c / 3. Las escaleras de Hickerson crecen a velocidades de 4 c / 9, 4 c / 10 y 4 c / 13. [7]
Simulación de circuitos
Las escaleras en Vida sin muerte se pueden usar para simular circuitos booleanos arbitrarios : [6] la presencia o ausencia de una escalera en una posición determinada puede usarse para representar una señal booleana, y diferentes interacciones entre pares de escaleras o entre escaleras y patrones de naturaleza muerta, se pueden utilizar para simular las puertas "y", "o" y "no" de la lógica booleana, así como los puntos donde dos señales se cruzan. Por lo tanto, es P-completo simular patrones en la regla Vida sin muerte, lo que significa que es poco probable que exista un algoritmo paralelo para una simulación significativamente más rápida que la obtenida por un algoritmo paralelo ingenuo con un procesador por celda de autómata celular y un paso de tiempo. por generación del patrón. [6]
Crecimiento infinito
Los patrones de semillas en forma de bolas de un radio de hasta diez generalmente conducen a un patrón de naturaleza muerta ; [4] sin embargo, Gravner [8] sugiere que la regla es supercrítica, lo que significa que las semillas más grandes o menos simétricas típicamente se expanden para siempre de forma caótica. Las escaleras son un fenómeno frecuente en los límites de las regiones de crecimiento caótico.
Se dice que un patrón en Vida sin muerte llena el plano con densidad positiva si hay algún radio r tal que cada celda del plano esté eventualmente dentro de la distancia r de una celda viva. Gravner, Griffeath y Moore plantearon la cuestión de si existen patrones de crecimiento tan infinitos como un problema abierto. [4] [6] Los patrones caóticos comunes en esta regla pueden llenar el plano, pero también pueden dejar grandes regiones rectangulares vacías enmarcadas por escaleras, haciendo que fallen la condición de densidad. Sin embargo, en 2009 Dean Hickerson encontró patrones de expansión diagonal que eventualmente se establecieron en un crecimiento infinito de período alto, resolviendo el problema abierto. [7]
Notas
- ^ Toffoli, Tommaso ; Margolus, Norman (1987), "1.2 Animate-by-numbers", Cellular Automata Machines: A New Environment for Modeling , MIT Press, págs. 6–7.
- ^ MCell léxico de las reglas de los autómatas celulares .
- ^ Esta definición de vecinos se conoce como barrio de Moore .
- ^ a b c d e Gravner, Janko; David, Griffeath (1998), "Crecimiento de autómatas celulares en Z 2 : Teoremas, ejemplos y problemas", Avances en matemáticas aplicadas , 21 : 241–304, doi : 10.1006 / aama.1998.0599.
- ^ Seusa lanotación c , yc se llama velocidad de la luz , porque es la velocidad más rápida a la que la información puede propagarse a través de un autómata celular que usa la vecindad de Moore.
- ^ a b c d Griffeath, David; Moore, Cristopher (1996), "Life without Death is P-complete" , Complex Systems , 10 : 437–447.
- ^ a b Eppstein, David (2009), Escaleras más rápidas en Vida sin muerte.
- ^ Gravner, Janko (2003), "Los fenómenos de crecimiento en autómatas celulares", Nuevas construcciones en autómatas celulares , Estudios del Instituto Santa Fe en las Ciencias de la Complejidad, Oxford University Press, págs. 161-182, archivado desde el original en 2010-06- 26
enlaces externos
- A Way-Cool CyberFlake y Life Without Death (Revisited) , del sitio web del autómata celular Primordial Soup Kitchen.
- Vida sin muerte en LifeWiki.