Juego de la vida

"Conway juego" puede referirse a los juegos como se define por números surreales, que Conway también desarrolló.

De Gosper Planeador Pistola crear " planeadores ".

El Juego de la Vida es un autómata celular diseñado por el británico matemático John Horton Conway en 1970. Es el ejemplo más conocido de un autómata celular.

El "juego" es en realidad un -jugador cero juego, lo que significa que su evolución está determinada por su estado inicial, sin necesidad de aporte de los jugadores humanos. Uno interactúa con el juego de la vida mediante la creación de una configuración inicial y observar cómo evoluciona. Una variante existe donde dos jugadores compiten.

Reglas

El universo del juego de la vida es una infinita red ortogonal bidimensional de celdas cuadradas, cada una de ellas se encuentra en uno de dos estados posibles, vivos o muertos. Cada célula interactúa con sus ocho vecinos, que son las células que son directamente horizontal, vertical o diagonalmente adyacente. En cada paso en el tiempo, se producen las siguientes transiciones:

1. Cualquier célula viva con menos de dos vecinos vivos muere, como si por la soledad.
2. Cualquier célula viva con más de tres vecinos vivos muere, como si por el hacinamiento.
3. Cualquier célula viva con dos o tres vecinos vivos vive, sin cambios, a la siguiente generación.
4. Cualquier célula muerta con exactamente tres vecinos vivos vuelve a la vida.

El patrón inicial constituye la "semilla" del sistema. La primera generación se crea mediante la aplicación de las reglas anteriores simultáneamente a todas las células de la semilla - nacimientos y muertes ocurren simultáneamente, y el momento discreta a la que esto sucede a veces se llama una garrapata. (En otras palabras, cada generación es una pura función de la anterior.) Las reglas se siguen aplicando varias veces para crear más generaciones.

Orígenes

Conway estaba interesado en un problema que se presenta en la década de 1940 por el famoso matemático John von Neumann , que intentó encontrar una máquina hipotética que podría crear copias de sí mismo y tuvo éxito cuando se encontró un modelo matemático para una máquina de este tipo con reglas muy complicadas en una cuadrícula rectangular . Conway intentó simplificar las ideas de von Neumann y finalmente tuvo éxito. Mediante el acoplamiento de su éxito anterior con El problema de la sanguijuela en la teoría de grupos con su interés por las ideas de von Neumann relativos máquinas autorreplicantes, Conway ideó el juego de la vida.

Hizo su primera aparición pública en la edición de octubre 1970 Scientific American, en Martin Gardner " Juegos Matemáticos "columna. Desde un punto de vista teórico, es interesante porque tiene el poder de un máquina universal de Turing: es decir, cualquier cosa que se puede computar algorítmicamente se puede calcular dentro de Juego de la vida. Gardner escribió:

El juego hizo Conway inmediatamente famoso, pero también abrió un nuevo campo de investigación matemática, el campo de la autómatas celulares ... Debido a las analogías de la vida con el auge, caída y transformaciones de una sociedad de organismos vivos, que pertenece a una clase creciente de los llamados "juegos de simulación '(juegos que se asemejan a los procesos de la vida real)

Desde su publicación, Juego de la vida ha atraído mucho interés debido a las formas sorprendentes en el que los patrones pueden evolucionar. La vida es un ejemplo de surgimiento y autoorganización. Es interesante para los físicos , biólogos , economistas , matemáticos , filósofos , científicos generativos y otros para observar la forma en que los patrones complejos pueden surgir de la aplicación de reglas muy simples. El juego puede también servir como una didáctica analogía, que se utiliza para transmitir la noción poco intuitivo que el "diseño" y "organización" pueden surgir de forma espontánea en ausencia de un diseñador. Por ejemplo, el filósofo y científico cognitivo Daniel C. Dennett ha utilizado el análogo de "universo" de Conway Vida ampliamente para ilustrar la posible evolución de las construcciones filosóficas complejas, como conciencia y libre albedrío, de la relativamente simple conjunto de leyes físicas deterministas que rigen nuestro propio universo.

La popularidad de la Vida de Conway fue ayudado por el hecho de que nació justo a tiempo para una nueva generación de bajo costo minicomputadoras que estaban siendo liberados en el mercado, lo que significa que el juego podría ser ejecutado por horas en estas máquinas que eran de otra manera sin usar por la noche. A este respecto, prefigura la popularidad posterior de generados por ordenador fractales . Para muchos, la vida era simplemente un desafío de programación, una forma divertida de perder CPU ciclos. Para algunos, sin embargo, la vida tenía connotaciones más filosóficos. Se desarrolló un culto a través de las décadas de 1970 y más allá; los recientes acontecimientos han ido tan lejos como para crear emulaciones teóricos de los sistemas informáticos en los confines de un tablero de la Vida.

Conway escogió a sus reglas cuidadosamente, después de una considerable experimentación, para cumplir con tres criterios:

1. No debe haber ningún patrón inicial para la que no es una prueba simple que la población puede crecer sin límite.
2. No debe haber patrones iniciales que aparentemente crecen sin límite.
3. No debe haber patrones iniciales simples que crecen y cambian durante un período considerable de tiempo antes de llegar a su fin en las siguientes maneras:

   • Desapareciendo completamente (de hacinamiento o llegue a ser demasiado escaso); o
   • Instalarse en una configuración estable que se mantiene sin cambios a partir de entonces, o entrar en una fase de oscilación en la que repiten un ciclo interminable de dos o más períodos.

Ejemplos de patrones

La evolución y el movimiento de un planeador.

La evolución y el movimiento de un LWSS.

Hay muchos tipos de patrones se producen en el juego de la vida, incluidos los patrones estáticos (" naturalezas muertas "), la repetición de patrones (" osciladores "- un superconjunto de naturalezas muertas), y patrones que se traducen a sí mismos a través del tablero (" naves espaciales "). Los ejemplos más comunes de estas tres clases se muestran a continuación, con células vivas muestran en negro, y las células muertas aparecen en blanco.

Block (naturaleza muerta)
Barco (naturaleza muerta)
Blinker (bifásico oscilador)
Toad (bifásico oscilador)
Planeador (nave espacial)
Nave espacial (Lightweight LWSS)
Pulsar (oscilador de tres fases)

El "púlsar" es el más común período de 3 oscilador. La gran mayoría de los osciladores de origen natural son el periodo 2, al igual que la luz intermitente y el sapo, pero los períodos de 4, 8, 15, 30, y algunos otros se han visto en raras ocasiones .

Los patrones llamados " Matusalenes "puede evolucionar durante largos períodos antes de repetir." Intransigente "es un patrón que eventualmente desaparece después de 130 generaciones, o pasos." Acorn "tarda 5.206 generaciones para generar al menos 25 planeadores y estabilizar la mayor cantidad de osciladores.

Diehard	Bellota

Conway originalmente conjeturó que ningún patrón puede crecer indefinidamente - es decir, que para cualquier configuración inicial con un número finito de células vivas, la población no puede crecer más allá de cierto límite superior finito. En el aspecto original del juego en " Juegos Matemáticos ", Conway ofreció un premio de $ 50 a la primera persona que podría probar o refutar la conjetura antes de finales de 1970. Una forma de probar lo contrario sería descubrir patrones que seguir sumando contadores para el campo: una" pistola ", que sería una configuración que dispara repetidamente objetos en movimiento, como el "planeador", o un "tren del fumador", lo que sería una configuración que se mueve, pero deja tras de sí un rastro de "humo" persistente.

El premio fue ganado en noviembre del mismo año por un equipo de la Instituto de Tecnología de Massachusetts, dirigido por Bill Gosper; el "arma Gosper" se muestra a continuación produce su primer planeador en la 15ta generación, y otro planeador cada generación 30a a partir de entonces. Esta primera arma planeador es aún el más pequeño conocido:

Patrones más simples eran tarde se descubrió que también exhiben un crecimiento infinito. Los tres de los siguientes patrones de crecer indefinidamente: las dos primeras crear un motor "bloque de colocación de" interruptor de cada uno, mientras que el tercero crea dos. La primera tiene sólo 10 células vivas (que se ha demostrado ser mínima). El segundo cabe en un cuadrado de 5 × 5. El tercero es sólo una célula de alta:

Descubrimientos posteriores incluyeron otros " armas de fuego ", que son estacionarios y disparan planeadores u otras naves espaciales"; peces globo ", que se mueven a lo largo dejando atrás una estela de escombros, y" rastrillos ", que se mueven y emiten naves espaciales. Gosper también construyó el primer modelo con un asintóticamente óptima tasa de crecimiento cuadrática, llamada " obtentor ", o" langosta ", que trabajó al dejar atrás un rastro de las armas.

Es posible que los planeadores interactúen con otros objetos en formas interesantes. Por ejemplo, si dos planeadores se filman a una cuadra de la manera correcta, el bloque se moverá más cerca de la fuente de los planeadores. Si tres planeadores se tiran en la manera correcta, el bloque se moverá más lejos. Esta "memoria bloque deslizante" se puede utilizar para simular un mostrador. Es posible construir puertas lógicas tales como Y, O y NO usar planeadores. Es posible construir un modelo que actúa como una máquina de estado finito conectado a dos contadores. Esto tiene el mismo poder computacional como máquina universal de Turing, por lo que el juego de la vida es tan poderoso como cualquier computadora con memoria ilimitada: es Turing completo. Además, un patrón puede contener una colección de armas de fuego que se combinan para construir nuevos objetos, incluyendo copias del patrón original. Un "constructor universal" se puede construir, que contiene una computadora completa de Turing, y que puede construir muchos tipos de objetos complejos, incluyendo más copias de sí mismo.

Iteración

A partir de un patrón inicial aleatoria de las células vivas en la parrilla, los observadores se encuentra la población en constante cambio como las generaciones por garrapatas. Los patrones que emergen de las reglas simples pueden considerarse una forma de belleza. Pequeños subpatrones aisladas sin simetría inicial tienden a convertirse simétrico. Una vez que esto sucede, la simetría puede aumentar en la riqueza, pero no se pierde, salvo un sub-patrón cercano se acerca lo suficiente a perturbarlo. En muy pocos casos, la sociedad finalmente se extingue, con todas las células vivas de fuga, aunque esto no puede suceder por un gran número de generaciones. La mayoría de los modelos iniciales, finalmente, "se queman", produciendo así cifras estables o patrones que oscilan siempre entre dos o más Estados; muchos de ellos también producen una o más planeadores o naves espaciales que viajan indefinidamente lejos de la ubicación inicial.

Algoritmos

Conway descubrió que el F- pentominó no logró estabilizarse en un pequeño número de generaciones.

Los primeros resultados en el juego de la vida se han obtenido sin el uso de computadoras. Los más sencillos bodegones y osciladores fueron descubiertas durante el seguimiento de los destinos de varias configuraciones de partida pequeños utilizando papel cuadriculado, pizarras, tableros de juego físicas (como Go ) y similares. Durante estas primeras investigaciones, Conway descubrió que el F- pentominó (que él llamó la "R-pentominó") no logró estabilizarse en un pequeño número de generaciones.

Estos descubrimientos inspirados programadores de computadoras alrededor del mundo para escribir programas para realizar un seguimiento de la evolución de los patrones de la vida. La mayor parte de los primeros algoritmos fueron similares. Representaban Patrones de vida como matrices bidimensionales en la memoria del ordenador. Normalmente se utilizan dos matrices, una para sujetar la generación actual y en el que para calcular su sucesor. A menudo, 0 y 1 representan las células vivas y muertas, respectivamente. Un bucle doble considera cada elemento de la matriz actual a su vez, contando los vecinos en vivo de cada célula para decidir si el elemento correspondiente de la matriz sucesor debería ser 0 o 1. Se muestra el array sucesor. Para la siguiente iteración los arrays intercambian los papeles para que la matriz sucesor en la última iteración se convierte en la matriz actual en la siguiente iteración.

Una variedad de mejoras de menor importancia a este esquema básico son posibles, y hay muchas maneras de ahorrar cálculo innecesario. Una célula que no cambió en el último paso del tiempo, y ninguno de cuyos vecinos cambiado, está garantizada para no cambiar en el paso de tiempo actual, así, por lo que un programa que realiza un seguimiento de las áreas que están activos puede ahorrar tiempo al no actualizar el zonas inactivas.

En principio, el campo de la vida es infinita, pero las computadoras tienen una memoria finita, y por lo general los tamaños de matriz debe ser declarado con antelación. Esto conduce a problemas cuando el área activa invade en la frontera de la matriz. Los programadores han utilizado varias estrategias para hacer frente a estos problemas. La estrategia más simple es simplemente asumir que todas las células fuera de la matriz está muerto. Esto es fácil de programar, pero conduce a resultados inexactos cuando el área activa cruza el límite. Un truco más sofisticada es considerar los bordes izquierdo y derecho del campo para ser cosidas juntas, y los bordes superior e inferior también, produciendo un toroidal matriz. El resultado es que las áreas activas que se mueven a través de un borde del campo vuelven a aparecer en el borde opuesto. La inexactitud aún puede resultar si el patrón es demasiado grande, pero al menos no hay efectos de borde patológicos. Las técnicas de asignación de almacenamiento dinámica también pueden ser utilizados, la creación de matrices cada vez más grandes para mantener los patrones de crecimiento.

Alternativamente, el programador puede abandonar la idea de representar el campo de la vida con una matriz de 2 dimensiones, y el uso de una estructura de datos diferente, como un vector de pares de coordenadas que representan las células vivas. Este enfoque permite que el patrón se mueva sobre el campo sin obstáculos, mientras la población no supera el tamaño de la matriz vivo de coordenadas. El inconveniente es que el conteo de los vecinos en directo se convierte en una operación de búsqueda, lo que frena la velocidad de simulación. Con las estructuras de datos más sofisticados este problema también se puede resolver en gran parte.

Para explorar los patrones grandes en las grandes profundidades de tiempo, algoritmos sofisticados como Hashlife puede ser útil.

Variaciones sobre la Vida

Desde su creación original, de la vida, se han desarrollado nuevas reglas. El juego estándar de vida, en el que una célula "nace" si tiene exactamente 3 vecinos, se queda con vida si tiene 2 o 3 vecinos vivos, y muere de lo contrario, se simboliza como "23/3". El primer número, o una lista de números, es lo que se requiere para una celda para continuar. El segundo conjunto es el requisito para el nacimiento. De ahí que "16/6" significa "una célula nace si hay 6 vecinos, y vive en si hay 1 o 6 vecinos". HighLife es 23/36, porque tener 6 vecinos, además de la regla del juego original 23/3, causa un nacimiento. HighLife es mejor conocido por sus replicadores. Existen variaciones adicionales en la vida, aunque la gran mayoría de estos universos son demasiado caótico o desolado.

Una muestra de un oscilador de 48 etapas a partir de un juego 2D hexagonal de la Vida (artículo 34/2).

Algunas variaciones se modifica la geometría del universo, así como la regla. Las variaciones anteriores pueden ser considerados como la Plaza 2D, porque el mundo es bidimensional y se presentarán en una cuadrícula. Cuadrados 3D y cuadrados 1D variaciones se han desarrollado, al igual que las variaciones hexagonales 2D donde la red es hexagonal o triangular en lugar de cuadrado.

Reglas de Conway también pueden ser generalizados para que en lugar de dos estados (vivos y muertos), hay tres o más. Las transiciones de estado se determinan ya sea por un sistema de ponderación o por una tabla que especifica reglas de transición separadas para cada estado; por ejemplo, Multicolor "Reglas Tabla" de Mirek Cellebration y "Vida ponderado" familias de reglas incluyen cada uno reglas de muestra equivalentes a la Vida de Conway.

Patrones relacionados con los fractales y sistemas fractales también se pueden observar en ciertas variaciones de la Vida-como. Por ejemplo, el autómata 12/1 genera cuatro aproximaciones muy cerca de la Triángulo de Sierpinski cuando se aplica a una sola célula en vivo.

La inmigración es una variación que es el mismo que el juego de la vida, excepto que hay dos en los estados (a menudo expresado en dos colores diferentes). Cada vez que nace una nueva célula, adquiere el estado ON que es la mayoría en las tres celdas que le dieron origen. Esta característica se puede utilizar para examinar las interacciones entre naves espaciales y otros "objetos" en el juego. Otra variación similar, llamado QuadLife, involucra cuatro diferentes Estados. Cuando una nueva célula nace de tres maneras vecinos, adquiere el cuarto valor, y de otra manera como la inmigración que toma el valor de la mayoría. Excepto por la variación entre en las células, tanto de estas variaciones actúan de forma idéntica a la Vida.

Variación para dos jugadores

En esta variación, las células vivas pueden tener dos colores y un jugador gana cuando se eliminan todas las células del color del contrario. Cuando una célula muerta se convierte en vivo, su color es determinado por el color dominante de sus células vivas vecinas (que son exactamente tres), como en el de Inmigración antes mencionado. Comience con un patrón de partida aleatoria o pre elegido con la mitad de las células vivas de cada color. Después de una iteración, el primer jugador puede añadir una célula de su color y eliminar una célula del color de su oponente. Después de la siguiente iteración el otro jugador puede hacer lo mismo, y así sucesivamente.

Programas de Vida notables

El primer programa de la vida fue escrita para el PDP-7 por MJT Guy y SR Bourne en 1970. Sin su ayuda algunos descubrimientos sobre el juego habría sido difícil de hacer.

En la actualidad hay miles de programas de Vida en línea, por lo que una lista completa no se proporcionan aquí. La siguiente es una selección de un pequeño número de programas con algún derecho especial a la notabilidad, como la popularidad o características inusuales. La mayoría de estos programas incorporan una interfaz gráfica de usuario para la edición de patrones y la simulación, la capacidad para simular varias reglas incluyendo la vida, y una gran biblioteca de patrones interesantes en la vida y otras normas CA.

• Juego de la vida de Alan Hensel. Un applet de Java Web emergente con algoritmos de simulación rápidas y una gran biblioteca de patrones de vida interesante.
• Golly. Una multiplataforma (Windows, Macintosh y Linux) de código abierto sistema de simulación de la vida de Andrew Trevorrow y Tomas Rokicki incluyendo la algoritmo Hashlife para la generación extremadamente rápido y Python guionización tanto para la edición y simulación.
• Life32. Freeware para máquinas Windows incluye potentes funciones de edición de secuencias de comandos y patrón.
• Cellebration de Mirek. Libre 1-D y 2-D espectador autómatas celulares, explorador y editor para Windows. Incluye poderosas instalaciones para la simulación y visualización de una amplia variedad de normas CA incluyendo la Vida, y un editor de scripts.
• Xlife Un laboratorio celular autómata por Jon Bennett. La aplicación de simulación de Linux estándar de vida mucho tiempo, sino que también ha sido portado a Windows. Puede manejar reglas autómata celular con el mismo barrio que la vida y hasta ocho estados posibles por célula. Ver aquí por muchas versiones alternativas.