theory - pelicula - ¿Por qué el Juego de la vida de Conway puede clasificarse como una máquina universal?
juego de la vida 3d (5)
Hace poco estuve leyendo sobre vida artificial y me encontré con la afirmación: "El juego de la vida de Conway demuestra bastante complejidad como para clasificarse como una máquina universal". Solo tenía una comprensión aproximada de lo que es una máquina universal , y Wikipedia solo me trajo tan cerca de la comprensión como lo hace Wikipedia. Me pregunto si alguien podría arrojar algo de luz sobre esta afirmación tan sexy.
El Juego de la vida de Conway parece, para mí, ser una distracción encantadora con algunas implicaciones tremendas: ¿no puedo dar el salto entre eso y la calculadora? ¿Es eso incluso el salto que debería estar haciendo?
Paul Rendell implementó una máquina de Turing en Life . Los planeadores representan señales, y las interacciones entre ellos son puertas y lógica que juntas pueden crear componentes más grandes que implementan la máquina de Turing.
Básicamente, cualquier maquinaria automática que pueda implementar AND, OR y NOT puede combinarse de manera suficientemente compleja para ser completa. No es una forma útil de calcular, pero cumple los criterios.
Puedes construir una máquina de Turing fuera de la vida de Conway, aunque sería bastante horrendo.
La clave está en los planeadores (y patrones relacionados), estos se mueven (lentamente) a lo largo del campo de juego, por lo que pueden representar corrientes de bits (la presencia de un planeador para un 1 y la ausencia de un 0). Se pueden construir otros patrones para tomar dos flujos de planeadores (en ángulo recto) y emitir otro flujo de bits correspondiente al AND / OR / etc de las dos corrientes originales.
EDITAR: hay más sobre esto en el sitio web de LogiCell .
Recomiendo mucho el libro The Recursive Universe de Poundstone. Agotado, pero probablemente pueda encontrar una copia, quizás en una buena biblioteca. Es casi todo sobre el poder de la vida de Conway, y las cosas que pueden existir en un universo con ese conjunto de leyes naturales, incluidas las entidades de autorreproducción y el IIRC, la evolución darwiniana.
Y Paul Chapman realmente construye una máquina de turing universal con el juego de la vida: http://www.igblan.free-online.co.uk/igblan/ca/ mediante la construcción de una "máquina universal de registro de Minsky".
El patrón está construido sobre una red de 30x30 cuadrados. Las naves espaciales livianas (LWSS) se utilizan para comunicarse entre componentes, que tienen lógica P60 (excepto para los registros, ver a continuación). Un LWSS tarda 60 generaciones en cruzar un cuadrado de celosía. Cada 60 generaciones, por lo tanto, cualquier LWSS (pulso) entre componentes se encuentra en la misma posición con respecto al cuadrado en el que se encuentra, lo que permite la rotación
.
La "Vida" de Conway puede tomarse aún más: no solo es posible construir un patrón de Vida que implemente una Máquina Universal de Turing, sino también un "Constructor Universal" de Von Neumann: http://conwaylife.com/wiki/Universal_constructor
Dado que un "Constructor Universal" puede ser programado para construir cualquier patrón de células, incluyendo una copia de sí mismo, la "Vida" de Coway es por lo tanto capaz de "autorreplicación", no solo de Computación Universal.