¿Por qué puede Juego de la vida puede clasificar como una máquina universal?

Question

Hace poco leí sobre la vida artificial y se encontró con la declaración, "Juego de Conway de la vida demuestra la complejidad suficiente para ser clasificado como una máquina universal " que sólo tenía un conocimiento aproximado de lo que un máquina universal es y Wikipedia solamente me trajo lo más cercano a la comprensión como Wikipedia lo hace. Me pregunto si alguien puede arrojar algo de luz sobre esta declaración muy atractiva?

Juego de la vida parece, para mí, ser una distracción preciosa, con algunos enormes implicaciones: no puedo dar el salto entre eso y la calculadora? Es que incluso el salto que yo debería estar haciendo?

Answer 1

pueden construir una máquina de Turing de la vida de Conway - aunque sería bastante horrible

.

La clave está en planeadores (y patrones relacionados) - éstos movimiento (lentamente) a lo largo del campo de juego, por lo que puede representar flujos de bits (la presencia de un planeador por un 1 y la ausencia de un 0). Otros patrones se pueden construir para tomar en dos corrientes de planeadores (en ángulo recto) y emitir otro flujo de bits correspondiente a la Y / O / etc de las dos corrientes originales.

EDIT:. Para más información sobre esto en el LogiCell sitio web

Answer 2

Paul Rendell implementa una máquina de Turing en la vida . Planeadores representan señales, y las interacciones entre ellos son puertas y lógica que juntos pueden crear componentes más grandes que implementan la máquina de Turing.

Básicamente, cualquier maquinaria automática que puede aplicar AND, OR y NOT se pueden combinar entre sí de una manera lo suficientemente complejo como para ser Turing completo. No es una forma útil de calcular, pero que cumple con los criterios.

Answer 3

"La vida" de Conway se puede tomar aún más: No sólo es posible construir un modelo de vida que implementa una máquina universal de Turing, sino también un Von Neumann "Constructor universal:" http://conwaylife.com/wiki/Universal_constructor

Desde un "Universal Constructor" se puede programar para construir cualquier patrón de células, incluyendo una copia de sí mismo, "Life" de coway es por lo tanto capaz de "auto-replicación", no sólo universal Computación.

Answer 4

Le recomiendo el libro El Universo recursiva por Poundstone. Fuera de impresión, pero es probable que pueda encontrar una copia, tal vez 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 autorreproductores y IIRC, la evolución darwiniana.

Answer 5

Y Paul Chapman realmente construir una máquina universal de Turing con el juego de la vida: http://www.igblan.free-online.co.uk/igblan/ca/ mediante la construcción de un "universal Minsky Registro de la máquina".

  

El patrón se construye en una   celosía de cuadrados 30x30. Ligero   Naves Espaciales (LWSSs) se utilizan para   la comunicación entre componentes, la cual   tiene lógica P60 (a excepción de Registros -   vea abajo). A LWSS toma 60   generaciones para cruzar un cuadrado de celosía.   Cada 60 generaciones, por lo tanto, cualquier   entre componentes LWSS (pulso) está en el   misma posición relativa a la plaza   que se encuentra, lo que permite la rotación

.