Pourquoi Conway Jeu de la Vie, être classé comme une machine universelle?

Question

J'ai récemment été la lecture sur la vie artificielle et est venu à travers la déclaration, "Conway Jeu de la Vie démontre suffisamment de complexité pour être classé comme une machine universelle." Je n'avais qu'un accidenté de la compréhension de ce qu'est une machine universelle est, et Wikipédia n'a apporté moi en tant que proche de compréhension, comme Wikipédia le fait jamais. Je me demande si quelqu'un pourrait jeter quelque lumière sur ce très sexy déclaration?

Conway Jeu de la Vie me semble, à moi, d'être une belle distraction avec certains d'énormes implications: je ne peux pas faire le saut entre ça et le calculateur? C'est que même le saut que je dois faire?

Answer 1

Paul Rendell mis en place une machine de Turing dans la Vie. Les planeurs de représenter les signaux, et les interactions entre eux sont des portes et de la logique, qui, ensemble, peuvent créer de gros de composants qui mettent en œuvre la machine de Turing.

Fondamentalement, toutes les machines automatiques qui peuvent mettre en œuvre ET, OU, et NE peuvent être combinés ensemble dans un complexe assez de moyens pour être Turing-complet. Il n'est pas utile de calculer, mais il répond aux critères.

Answer 2

Vous pouvez construire une machine de Turing de Conway de la vie - bien qu'il serait assez horrible.

La clé est dans planeurs (et les motifs) - ceux-ci évoluent (lentement) le long du terrain de jeu, de sorte que peut représenter le flux de bits (la présence d'un planeur par un 1, et l'absence d'un 0). D'autres modèles peuvent être construits de manière à prendre en deux flux de planeurs (à angle droit) et émettent un autre flux de bits correspondant à la ET/OU/etc de l'origine de deux ruisseaux.

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

Answer 3

Conway "Vie" peut être encore plus loin: non seulement Il est possible de construire un schéma de Vie qui implémente une Machine de Turing Universelle, mais aussi un Von Neumann "Universelle Constructeur:" http://conwaylife.com/wiki/Universal_constructor

Depuis un "Universel Constructeur" peut être programmé pour construire un schéma de cellules, y compris une copie de lui-même, Coway "la Vie" est donc capable de "s'auto-répliquer," non seulement le Calcul Universel.

Answer 4

Oh, ça va mieux: Wolfram est plus Simple Connu Machine de Turing. Wang Tuiles.

Answer 5

Je recommande fortement le livre de L'Récursive de l'Univers en Poundstone. Épuisé, mais vous pouvez probablement trouver une copie, peut-être dans une bonne bibliothèque. C'est presque tout au sujet de la puissance de Conway de la Vie, et les choses qui peuvent exister dans un univers avec cet ensemble de lois naturelles, y compris l'auto-reproduction des entités et IIRC, l'évolution Darwinienne.