Pourquoi peut-jeu de la vie de Conway est classé comme une machine universelle?

Question

Je lisais récemment sur la vie artificielle et suis tombé sur la déclaration, "Jeu de Conway de la vie démontre assez la complexité d'être classés comme une machine universelle. « Je ne ai eu une compréhension approximative de ce qu'est un machine universelle est, et Wikipédia ne m'a apporté que près de la compréhension que Wikipédia ne jamais. Je me demande si quelqu'un pouvait faire la lumière sur cette déclaration très sexy?

jeu de la vie de Conway me semble, à, être une belle distraction avec certains implications énormes: Je ne peux pas faire le saut entre cela et calculatrice? Est-ce même le saut que je devrais gagner?

Answer 1

peut construire une machine de Turing sur la vie de Conway - bien qu'il serait assez horrible

.

La clé est dans planeurs (et modèles connexes) - ces mouvements (lentement) le long du terrain de jeu, peut donc représenter les flux de bits (la présence d'un planeur pour 1 et l'absence de a 0). D'autres motifs peuvent être construits pour prendre en deux courants de planeurs (à angle droit) et émettent un autre train de bits correspondant à l'ET / OU / etc originaux des deux courants.

EDIT:. Il y a plus à ce sujet LogiCell site web

Answer 2

Paul Rendell mis en place un machine de Turing de vie. Les ailes représentent des signaux, et les interactions entre eux sont des portes et une logique qui, ensemble, peuvent créer de plus grandes composantes qui mettent en oeuvre la machine de Turing.

En fait, toute machine automatique qui peut mettre en œuvre AND, OR, et ne peuvent être combinés ensemble de manière assez complexe pour être Turing-complet. Ce n'est pas un moyen utile de calculer, mais il répond aux critères.

Answer 3

Conway "La vie" peut être pris encore plus loin: Il est non seulement possible de construire un modèle de vie qui implémente une machine de Turing universelle, mais aussi un Von Neumann "Constructor Universal:" http://conwaylife.com/wiki/Universal_constructor

Depuis un « constructeur universel » peut être programmé pour construire une structure de cellules, y compris une copie de lui-même, « la vie » de Coway est donc capable de « l'auto-réplication, » non seulement calcul universel.

Answer 4

Je recommande fortement le livre L'Univers récursive par Poundstone. Epuisé, mais vous pouvez probablement trouver une copie, peut-être dans une bonne bibliothèque. Il est presque tout au sujet de la puissance de la vie de Conway, et les choses qui peuvent exister dans un univers avec cet ensemble de lois naturelles, y compris les entités autoreproductrices et IIRC, l'évolution darwinienne.

Answer 5

Et Paul Chapman construire effectivement une machine de Turing universelle avec jeu de la vie: http://www.igblan.free-online.co.uk/igblan/ca/ en construisant un "Minsky Universal enregistrer la machine".

  

Le schéma est construit sur un   treillis de carrés de 30x30. Poids léger   Vaisseaux (LWSSs) sont utilisés pour   communiquer entre les composants, qui   avoir une logique de P60 (à l'exception des registres -   voir ci-dessous). A LWSS prend 60   générations à traverser un carré en treillis.   Toutes les 60 générations, par conséquent, tout   LWSS inter-composant (impulsion) est dans la   même position par rapport au carré   il est en permettant une rotation

.