Conteúdo verificado

Jogo da Vida de Conway

Assuntos Relacionados: Matemática

Você sabia ...

Esta seleção Escolas foi originalmente escolhido pelo SOS Children para as escolas no mundo em desenvolvimento sem acesso à internet. Ele está disponível como um download intranet. Clique aqui para mais informações sobre Crianças SOS.

"Conway jogo" pode referir-se a jogos como definido pela números surreais, que Conway também desenvolvidos.
De Gosper Glider Gun criando " planadores ".

O jogo da vida é um autômato celular concebido pelo britânico matemático John Horton Conway em 1970. Ele é o exemplo mais conhecido de um autômato celular.

O "jogo" é realmente um de zero-jogador do jogo, o que significa que sua evolução é determinada pelo seu estado inicial, não necessitando de entrada de jogadores humanos. Uma interage com o jogo da vida através da criação de uma configuração inicial e observando como ele evolui. Uma variante existe quando dois jogadores competem.

Regras

O universo do Jogo da Vida é uma malha ortogonal bidimensional infinita de células quadradas, cada um dos quais está em um dos dois estados possíveis, vivo ou morto. Cada célula interage com os seus oito vizinhos, que são as células que estão directamente na horizontal, vertical ou diagonal adjacente. Em cada passo no tempo, os seguintes transições ocorrem:

  1. Qualquer célula viva com menos de dois vizinhos vivos morre, como se pela solidão.
  2. Qualquer célula viva com mais de três vizinhos vivos morre, como se pela superlotação.
  3. Qualquer célula viva com dois ou três vizinhos vivos vive, sem alterações, para a próxima geração.
  4. Qualquer célula morta com exatamente três vizinhos vivos vem à vida.

O padrão inicial constitui o "semente" do sistema. A primeira geração é criado através da aplicação das regras acima simultaneamente para todas as células na semente - nascimentos e mortes acontecem simultaneamente, e no momento discreto em que isso acontece às vezes é chamado um carrapato. (Em outras palavras, cada geração é uma função pura do que o anterior.) As regras continuam a ser aplicadas várias vezes para criar novas gerações.

Origins

Conway estava interessado em um problema apresentado na década de 1940 pelo renomado matemático John von Neumann , que tentou encontrar uma máquina hipotética que poderia construir cópias de si mesmo e conseguiu quando ele encontrou um modelo matemático para tal máquina com regras muito complicadas em uma grade retangular . Conway tentou simplificar as idéias de von Neumann e finalmente conseguiu. Ao acoplar seu sucesso anterior com O problema de sanguessuga em teoria de grupo com o seu interesse em idéias de von Neumann em matéria de máquinas de auto-replicantes, Conway inventou o Jogo da Vida.

Ele fez sua primeira aparição pública na outubro 1970 emissão de Scientific American, em Martin Gardner " Jogos Matemáticos "coluna. De um ponto de vista teórico, é interessante porque tem o poder de um Turing universal máquina: ou seja, qualquer coisa que pode ser computado através de algoritmos pode ser computada dentro Jogo da Vida de Conway. Gardner escreveu:

O jogo fez Conway famoso instantaneamente, mas também abriu um novo campo de investigação matemática, o campo de autômatos celulares ... Por causa de analogias da vida com a ascensão, queda e transformações de uma sociedade de organismos vivos, que pertence a uma classe crescente de que são chamados de "jogos de simulação '(jogos que lembram os processos da vida real)

Desde a sua publicação, Jogo da Vida de Conway tem atraído muito interesse por causa das maneiras surpreendentes em que os padrões podem evoluir. A vida é um exemplo de emergência e auto-organização. É interessante para os físicos , biólogos , economistas , matemáticos , filósofos , cientistas generativas e outros a observar a maneira que os padrões complexos podem surgir a partir da aplicação de regras muito simples. O jogo também pode servir como um didático analogia, utilizado para transmitir a noção um pouco contra-intuitivo que "design" e "organização" pode emergir espontaneamente na ausência de um designer. Por exemplo, filósofo e cientista cognitivo Daniel C. Dennett tem usado o análogo da Vida "universo" de Conway extensivamente para ilustrar a possível evolução das construções filosóficas complexas, como consciência e livre-arbítrio, a partir do relativamente simples conjunto de leis físicas que regem determinísticos nosso próprio universo.

A popularidade da Vida de Conway foi ajudado pelo fato de que ele passou a existir apenas a tempo para uma nova geração de baixo custo minicomputadores que estavam a ser lançado no mercado, o que significa que o jogo poderia ser executado por horas nessas máquinas que eram de outra maneira não utilizado à noite. A este respeito, prenunciou a popularidade depois de geradas por computador fractais . Para muitos, a vida era simplesmente um desafio de programação, uma maneira divertida de perder CPU ciclos. Para alguns, no entanto, a vida tinha conotações mais filosóficas. Ele desenvolveu um culto através das décadas de 1970 e além; desenvolvimentos atuais têm ido tão longe como para criar emulações teóricas de sistemas de computador dentro dos limites de uma placa de Vida.

Conway escolheu suas regras cuidadosamente, depois de considerável experimentação, para atender a três critérios:

  1. Não deve haver nenhum padrão inicial para o qual existe uma prova simples, que a população pode crescer sem limite.
  2. Deve haver padrões iniciais que aparentemente não crescem sem limites.
  3. Deve haver padrões iniciais simples que crescer e mudar para um período de tempo considerável antes de chegar ao fim das seguintes maneiras possíveis:
    • Desaparecendo completamente (de superlotação ou de se tornar demasiado escasso); ou
    • Fixando-se em uma configuração estável que permanece inalterado depois, ou entrando em uma fase de oscilação em que se repetir um ciclo interminável de dois ou mais períodos.

Os exemplos de padrões

A evolução eo movimento de um planador.
A evolução eo movimento de um LWSS.

Muitos tipos diferentes de padrões ocorrem no jogo da vida, incluindo padrões estáticos (" naturezas-mortas "), padrões repetitivos (" osciladores "- um super conjunto de naturezas-mortas), e padrões que se traduzem-se em toda a linha (" naves espaciais "). Exemplos comuns destes três classes são os indicados a seguir, com células vivas mostrados em preto, e as células mortas mostrado em branco.

Block (still life) Game of block.svg vida
Boat (still life) Game of boat.png vida
Blinker (de duas fases oscilador) Game of blinker.png vida
Sapo (em duas fases oscilador) Game of toad.png vida
Glider (nave espacial) Game of glider.png vida
Nave espacial leve (LWSS) Game of lwss.png vida
Pulsar (oscilador trifásica) 4demons.png

O "pulsar" é o período mais comum 3 oscilador. A grande maioria dos osciladores que ocorrem naturalmente são período de 2, como o pisca-pisca eo sapo, mas períodos de 4, 8, 15, 30, e alguns outros têm sido vistos em raras ocasiões, .

Padrões chamado " Methuselahs "pode evoluir por longos períodos antes de repetir." Duro de Matar "é um padrão que eventualmente desaparece após 130 gerações, ou passos." Acorn "leva 5206 gerações para gerar pelo menos 25 planadores e estabilizar como muitos osciladores.

Game of diehard.png vida Game of methuselah.png vida
Duro De Matar Bolota

Conway originalmente conjecturou que nenhum padrão pode crescer indefinidamente - ou seja, que para qualquer configuração inicial com um número finito de células vivas, a população não pode crescer além de algum limite superior finito. Na aparência original do jogo em " Jogos Matemáticos ", Conway ofereceu um prêmio de US $ 50 a primeira pessoa que poderia provar ou refutar a conjectura antes do final de 1970. Uma maneira de refutá-la seria descobrir padrões que manter-se adicionar contadores para o campo: a" arma ", o que seria uma configuração que dispara repetidamente objetos em movimento, tais como o "planador", ou um "trem do soprador", o que seria uma configuração que se move mas deixa para trás um rastro de "fumaça" persistente.

O prêmio foi conquistado em novembro do mesmo ano por uma equipe do Massachusetts Institute of Technology, liderado por Bill Gosper; a "arma Gosper" mostrada abaixo produz o seu primeiro planador na 15ª geração, e outro planador cada geração 30 a partir de então. Esta arma primeiro planador ainda é o menor conhecido:

Jogo da vida planador gun.png
Gosper Glider Gun

Padrões mais simples foram mais tarde descobriu que também apresentam crescimento infinito. Todos os três dos seguintes padrões crescer indefinidamente: os dois primeiros criar um mecanismo de switch "para a colocação de bloco" cada, enquanto a terceira cria dois. O primeiro tem apenas 10 células vivas (que tem sido provados para ser mínima). A segunda se encaixa em um 5 × 5 quadrados. O terceiro é apenas uma célula de alta:

Game of infinite1.png vida Game of infinite2.png vida

Game of infinite3.svg vida

Descobertas posteriores incluíram outro " armas ", que são estacionários e atirar para fora planadores ou outras naves espaciais"; baiacu ", que se movem ao longo deixando para trás um rastro de detritos; e" ancinhos ", que se movem e emitem naves espaciais. Gosper também construiu o primeiro padrão com um asymptotically ideal taxa de crescimento quadrática, chamado um " criador ", ou" lagosta ", que trabalhou por deixando para trás um rastro de armas.

É possível que os planadores para interagir com outros objetos em formas interessantes. Por exemplo, se dois planadores são filmados em um bloco em apenas o caminho certo, o bloco vai se aproximar da fonte dos planadores. Se três gliders são atirados em apenas o caminho certo, o bloco irá se mover mais longe. Esta "memória bloco deslizante" pode ser utilizado para simular uma balcão. É possível construir portas lógicas tais como E, OR e NÃO usando planadores. É possível construir um padrão que age como um máquina de estado finito conectada a dois contadores. Isto tem o mesmo poder computacional como um máquina universal de Turing, assim que o jogo da vida é tão poderoso quanto qualquer computador com memória ilimitada: é Turing completa. Além disso, um padrão pode conter uma coleção de armas que se combinam para construir novos objetos, incluindo cópias do padrão original. Um "construtor universal" pode ser construída que contém um computador completo Turing, e que pode construir muitos tipos de objectos complexos, incluindo mais cópias de si próprio.

Iteração

A partir de um padrão inicial aleatória de células vivas no grid, observadores encontrará a população em constante mutação como as gerações vão passando. Os padrões que emergem das regras simples pode ser considerado uma forma de beleza. Pequenas subpadrões isoladas sem simetria inicial tendem a se tornar simétrico. Uma vez que isso acontece, a simetria pode aumentar em riqueza, mas não pode ser perdido, a menos que um subpadrão nas proximidades chega perto o suficiente para perturbá-la. Em alguns poucos casos, a sociedade eventualmente morre para fora, com todas as células vivas de fuga, embora isso possa não acontecer por muitas gerações. A maioria dos padrões iniciais, eventualmente, "burn out", produzindo quer valores ou padrões que oscilam sempre entre dois ou mais estados estáveis; muitos também produzir uma ou mais planadores ou naves espaciais que viajam indefinidamente fora do local inicial.

Algoritmos

Conway descobriu que o F- pentominó não conseguiu estabilizar em um pequeno número de gerações.

Os primeiros resultados no Jogo da Vida foram obtidos sem o uso de computadores. Os mais simples naturezas-mortas e osciladores foram descobertos ao seguir o destino de várias configurações iniciais pequenas usando papel gráfico, quadros, placas de jogos físicos (como Go ) e similares. Durante esta pesquisa inicial, Conway descobriu que o F- pentomino (que ele chamou de "R-pentomino") não conseguiu estabilizar em um pequeno número de gerações.

Estas descobertas inspiradas programadores de computador todo o mundo para escrever programas para acompanhar a evolução dos padrões de vida. A maioria dos primeiros algoritmos foram semelhantes. Eles representavam padrões de vida como matrizes bidimensionais na memória do computador. Normalmente duas matrizes são usados, um para segurar a geração atual e aquele em que a calcular o seu sucessor. Muitas vezes, 0 e 1 representam células mortas e vivas, respectivamente. Um loop duplo considera cada elemento da matriz corrente, por sua vez, contando os vizinhos vivos de cada célula para decidir se o correspondente elemento da matriz sucessor deve ser 0 ou 1. A matriz é exibida sucessor. Para a próxima iteração as matrizes trocar de papéis para que a matriz sucessor na última iteração se torna a matriz atual na próxima iteração.

Uma variedade de pequenas melhorias a este esquema básico são possíveis, e há muitas maneiras de poupar computação desnecessária. Uma célula que não mudou no último passo de tempo, e nenhum dos vizinhos cuja alterado, é garantido que não mudam no intervalo de tempo atual, bem, então um programa que mantém o controle de quais áreas são ativos pode economizar tempo não atualizando o zonas inactivas.

Em princípio, o campo vida é infinita, mas os computadores têm memória finita, e geralmente tamanhos de matriz deve ser declarado com antecedência. Isto leva a problemas quando a área ativa invade a fronteira da matriz. Os programadores têm usado várias estratégias para resolver estes problemas. A estratégia mais simples é simplesmente assumir que todas as células fora da matriz está morto. Isto é fácil de programar, mas leva a resultados imprecisos quando a área activa atravessa a fronteira. Um truque mais sofisticado é considerar as bordas esquerda e direita do campo para ser costurado, e as bordas superior e inferior, obtendo-se também uma toroidal matriz. O resultado é que as áreas activas que se movem através de uma borda campo reaparecer no bordo oposto. Imprecisão ainda pode resultar se o padrão cresce muito grande, mas pelo menos não existem efeitos de borda patológicas. Técnicas de atribuição dinâmica de armazenamento também pode ser usado, a criação de conjuntos cada vez maiores para manter padrões de crescimento.

Em alternativa, o programador pode abandonar a noção de representar o campo vida com uma matriz de 2 dimensões, e usar uma estrutura de dados diferente, como um vetor de pares de coordenadas que representam células vivas. Esta abordagem permite que o padrão de se mover sobre o campo sem impedimentos, enquanto a população não exceda o tamanho da matriz de coordenadas vivo. A desvantagem é que a contagem vizinhos vivos se torna uma operação de busca, retardando a velocidade de simulação. Com as estruturas de dados mais sofisticados, este problema pode também ser resolvidos em grande parte.

Para explorar grandes padrões em grandes profundidades de tempo, algoritmos sofisticados como Hashlife pode ser útil.

Variações sobre vida

Desde a criação original de vida, novas regras têm sido desenvolvidos. O jogo padrão de vida, em que uma célula "nasce" se tem exatamente 3 vizinhos, permanece viva se tem 2 ou 3 vizinhos vivos, e morre em contrário, é simbolizado como "23/3". O primeiro número, ou uma lista de números, é o que é necessário para uma célula para continuar. O segundo conjunto é o requisito para o nascimento. Portanto "16/6" significa "uma célula nasce se há 6 vizinhos, e vive em se há 1 ou 6 vizinhos". HighLife é 23/36, porque tendo 6 vizinhos, além de 23/3 regra do jogo original, causa um nascimento. HighLife é mais conhecido por seus replicadores. As variações adicionais sobre a Vida existe, embora a grande maioria desses universos são ou muito caótico ou desolado.

Uma amostra de um oscilador de 48 etapas a partir de um jogo hexagonal 2D da Vida (regra 34/2).

Algumas variações modificar a geometria do universo, bem como a regra. As variações acima pode ser pensado como 2D Square, porque o mundo é bidimensional e dispostos em uma grade quadrada. Quadrados 3D e 1D quadrada variações têm sido desenvolvidos, assim como variações 2D hexagonais em que a grelha é hexagonal ou triangular em vez de quadrada.

Regras de Conway também pode ser generalizado de modo que em vez de dois estados (vivas e mortas), existem três ou mais. Transições de estado são, então, determinado quer por um sistema de ponderação ou por uma tabela que especifica regras de transição separados para cada estado; por exemplo, De Cellebration de Mirek multi-colorido "Regras Table" e "Life ponderada" regra famílias cada amostra incluir regras equivalentes a Vida de Conway.

Padrões, relativamente ao fractais e sistemas fractal também pode ser observada em determinadas variações Life-Like. Por exemplo, o autômato 12/1 gera quatro aproximações muito perto da Triângulo Sierpiński quando aplicado a uma única célula viva.

A imigração é uma variação que é o mesmo que o jogo da vida, exceto que há dois estados ON (muitas vezes expressa em duas cores diferentes). Sempre que uma nova célula nasce, ele assume o estado ON, que é a maioria nas três células que lhe deram origem. Este recurso pode ser utilizado para examinar as interacções entre naves espaciais e outros "objetos" dentro do jogo. Outra variação semelhante, chamado QuadLife, envolve quatro diferentes estados ON. Quando uma nova célula nasce de três diferentes ON vizinhos, ele assume o quarto valor, e de outra forma como a imigração leva o valor da maioria. Exceto para a variação entre nas células, essas duas variações agir de forma idêntica à Vida.

Variação para dois jogadores

Nesta variação, as células vivas pode ter duas cores e um jogador ganha quando todas as células de cor do oponente são eliminados. Quando uma célula se torna inoperante ao vivo, a sua cor é determinado pela cor dominante dos seus vizinhos (células vivas que são exactamente três), como acima mencionado na imigração. Comece com um padrão aleatório de partida ou pré-escolhida com metade das células vivas de cada cor. Depois de uma iteração, o primeiro jogador pode adicionar uma célula de sua cor e remover uma célula de cor de seu oponente. Após a iteração seguinte o outro jogador pode fazer o mesmo, e assim por diante.

Programas de Vida Notáveis

O primeiro programa Vida foi escrito para o PDP-7, MJT Guy e SR Bourne em 1970. Sem a sua ajuda algumas descobertas sobre o jogo teria sido difícil de fazer.

Existem hoje milhares de programas de vida on-line, de modo que uma lista completa não serão fornecidas aqui. A seguir está uma seleção de um pequeno número de programas com alguma reivindicação especial para a notabilidade, como popularidade ou características incomuns. A maioria destes programas incorporar uma interface gráfica para a edição padrão e simulação, a capacidade para simular várias regras, incluindo a vida, e uma grande biblioteca de padrões interessantes na vida e outras regras de AC.

  • Jogo da Vida de Conway por Alan Hensel. Um applet Java web pop-up com algoritmos de simulação rápidas e uma grande biblioteca de padrões de vida interessante.
  • Golly. A multi-plataforma (Windows, Macintosh e Linux) open-source sistema de simulação de vida por Andrew Trevorrow e Tomas Rokicki incluindo o algoritmo hashlife para a geração extremamente rápido e Python scriptability tanto para edição e simulação.
  • Life32. Freeware para máquinas Windows inclui recursos padrão de edição poderosas e programáveis.
  • Cellebration de Mirek. Grátis espectador autômatos celulares 1-D e 2-D, explorador e editor para Windows. Inclui instalações poderosas para simulação e visualização de uma grande variedade de regras incluindo CA Vida, e um editor de scripts.
  • Xlife Um laboratório celular-autômato por Jon Bennett. Há muito tempo que o aplicativo de simulação de vida padrão do Linux, ele também foi portado para o Windows. Pode lidar com regras autômato celular com o mesmo bairro como vida e até oito estados possíveis por célula. Ver aqui para muitas versões alternativas.
Retirado de " http://en.wikipedia.org/w/index.php?title=Conway%27s_Game_of_Life&oldid=205680804 "