El juego de la vida de Conway

Question

¿Existe alguna forma matemática de calcular directamente la iteración n a partir de la primera iteración saltándose el cálculo de las iteraciones intermedias en el Juego de la Vida de Conway? Supongo que, si es posible, se trataría de matrices.

Answer 1

No. La vida es Turing-completa - lo que significa que cada patrón de vida puede ser simulado por una máquina de Turing y viceversa - Así que, a falta de resolver el problema de la parada, la única forma de saber cómo acabará una configuración determinada es ejecutar la simulación.

Creo que eso se aplica a cualquier autómata celular, en realidad, no sólo a la vida (bueno, a excepción de las reglas en las que cada patrón muere o muestra un comportamiento predecible/consistente), aunque no estoy seguro de cómo demostrarlo para un autómata celular no Turing-completo.

Answer 2

Existen técnicas como HashLife para calcular rápidamente el estado a largo plazo de una configuración inicial.

Sin embargo, a cierto nivel se trata simplemente de una optimización que utiliza la memorización para aprovechar la redundancia del conjunto de reglas mediante quadtrees (una estructura de datos funcional utilizada aquí como una especie de representación deconstruida del campo).

Answer 3

Tu pregunta no es muy clara porque "calcular el n-ésimo paso saltándose los pasos intermedios" es difícil de formalizar. Sin embargo, Game of life es P-completo lo que significa que cualquier algoritmo de tiempo polinómico puede reducirse al problema de calcular el estado futuro de una célula en Game of Life. Por lo tanto, si usted tiene un algoritmo para predecir Juego de la vida que es rápido en el peor de los casos entonces se deducen algoritmos rápidos para cualquier problemas de tiempo polinómico, lo que es muy improbable incluso si se permite el paralelismo (cf. P vs. NC ). Hashlife funciona bien con entradas típicas o muy dispersas, pero no con todas las entradas.