Por que pode Jogo da Vida de Conway ser classificada como uma máquina universal?

Question

Recentemente eu estava lendo sobre a vida artificial e me deparei com a declaração ", o jogo de Conway of Life demonstra a complexidade suficiente para ser classificado como uma máquina universal. " eu só tinha uma compreensão aproximada do que um máquina universal é, e Wikipedia só me trouxe tão perto de compreender como a Wikipedia já faz. Gostaria de saber se alguém poderia lançar alguma luz sobre esta declaração muito sexy?

de Conway Game of Life parece, para mim, é um belo distração com algum tremendas implicações: Eu não posso dar o salto entre isso e calculadora? É que mesmo o salto que eu deveria estar fazendo?

Answer 1

Você pode construir uma máquina de Turing fora da vida de Conway -. Apesar de que seria muito horrendo

A chave está em planadores (e padrões relacionados) - estes se movem (lentamente) ao longo do campo de jogo, por isso pode representar fluxos de bits (a presença de um planador por um 1 ea ausência de um 0). Outros padrões podem ser construídos para levar em duas correntes de planadores (em ângulo reto) e emitem um outro fluxo de bits correspondente ao E / OU / etc dos dois fluxos originais.

EDIT: Há mais sobre isso na LogiCell web site

Answer 2

Paul Rendell implementou um máquina de Turing na vida . Planadores representam sinais, e as interações entre eles são portões e lógica que juntos podem criar componentes maiores que implementam a máquina de Turing.

Basicamente, qualquer tipo de equipamento automático que pode implementar AND, OR e NOT podem ser combinados de forma complexa o suficiente para ser Turing completo. Não é uma maneira útil de computação, mas cumpre os critérios.

Answer 3

O Conway "Life" pode ser levado ainda mais longe: Não é apenas possível construir um padrão de vida que implementa uma Máquina de Turing universal, mas também um Von Neumann "Universal Construtor:" http://conwaylife.com/wiki/Universal_constructor

Uma vez que um "Universal Construtor" pode ser programado para construir qualquer padrão de células, incluindo uma cópia de si mesmo, de Coway "Life" é, portanto, capaz de "auto-replicação," não apenas Universal Computação.

Answer 4

Eu recomendo o livro O recursiva Universo por Poundstone. Fora de catálogo, mas você pode provavelmente encontrar uma cópia, talvez em uma biblioteca boa. É quase tudo sobre o poder da Vida de Conway, e as coisas que podem existir em um universo com esse conjunto de leis naturais, incluindo entidades auto-reproduzir e IIRC, a evolução darwiniana.

Answer 5

E Paul Chapman realmente construir uma máquina de Turing universal com jogo da vida: http://www.igblan.free-online.co.uk/igblan/ca/ através da construção de um "Universal Minsky Register Machine".

O padrão é construído em um Estrutura de 30x30 quadrados. leve Naves espaciais (LWSSs) são usados ??para comunicar entre os componentes, que tem P60 lógica (exceto para Registros - ver abaixo). Um LWSS leva 60 gerações de atravessar um quadrado rede. A cada 60 gerações, portanto, qualquer LWSS inter-componente (impulso) está no mesma posição em relação ao quadrado que se encontra, permitindo a rotação

.