Perché può Gioco della vita essere classificato come una macchina universale?

Question

Recentemente stavo leggendo sulla vita artificiale e sono imbattuto la dichiarazione, "Gioco di Conway della vita dimostra abbastanza complessità deve essere classificato come una macchina universale " ho avuto solo una conoscenza approssimativa di ciò che una macchina universale è, e Wikipedia ha portato solo a me più vicino alla comprensione come Wikipedia fa mai. Mi chiedo se qualcuno potrebbe fare luce su questa affermazione molto sexy?

Gioco della vita sembra, per me, di essere una bella distrazione con un po ' implicazioni enormi: non riesco a fare il salto tra questo e calcolatrice? È che anche il salto che dovrebbe fare?

Answer 1

possono costruire una macchina di Turing dalla vita di Conway - anche se sarebbe abbastanza orrendo

.

La chiave è in vele (e modelli correlate) - questi mossa (lentamente) lungo il campo di gioco, quindi può rappresentare flussi di bit (la presenza di un aliante per un 1 e l'assenza di un 0). Altri modelli possono essere costruiti per prendere in due flussi di alianti (ad angolo retto) ed emettono un altro flusso di bit corrispondente a AND / OR / etc dei due flussi originali.

EDIT:. C'è di più su questo sul LogiCell sito

Answer 2

Paul Rendell implementato una macchina Turing nella vita . Vele rappresentano segnali, e le loro interazioni sono cancelli e logica che insieme possono creare componenti più grandi che implementano la macchina di Turing.

In sostanza, qualsiasi macchine automatiche in grado di implementare AND, OR e NOT possono essere combinati insieme in modi abbastanza complessi per essere Turing-completo. Non è un modo utile per calcolare, ma soddisfa i criteri.

Answer 3

"Life" di Conway può essere preso ancora di più: E 'non solo è possibile costruire un modello di vita che implementa una macchina di Turing Universale, ma anche un Von Neumann "Universal Costruttore:" http://conwaylife.com/wiki/Universal_constructor

Dal momento che un "costruttore universale" può essere programmato per costruire qualsiasi modello di cellule, tra cui una copia di se stesso, "Life" di Coway è quindi in grado di "auto-replicazione," non solo Universale di calcolo.

Answer 4

Consiglio vivamente il libro The Universe di ricorsiva Poundstone. Fuori stampa, ma probabilmente si può trovare una copia, magari in una buona biblioteca. E 'quasi tutto sul potere della vita di Conway, e le cose che possono esistere in un universo con quell'insieme di leggi naturali, compresi gli enti di auto-riproduzione e IIRC, l'evoluzione darwiniana.

Answer 5

E Paul Chapman in realtà costruire una macchina di Turing universale, con il gioco della vita: http://www.igblan.free-online.co.uk/igblan/ca/ con la costruzione di un "universale Minsky Registrati macchina".

  

Il modello è costruito su un   reticolo di quadrati 30x30. leggero   Astronavi (LWSSs) vengono utilizzati per   comunicare tra i componenti, che   hanno logica P60 (ad eccezione di Registri -   vedi sotto). Un LWSS prende 60   generazioni di attraversare una piazza reticolo.   Ogni 60 generazioni, di conseguenza, qualsiasi   fra componenti LWSS (impulso) è nella   stessa posizione rispetto al quadrato   si trova, consentendo di rotazione

.