thumb miniaturadaimagem|Uma única Arma de Planadores de Gosper criando planadores. O jogo da vida é um autómato celular desenvolvido pelo matemático britânico John Horton Conway em 1970. É o exemplo mais bem conhecido de autômato celular.
O jogo foi criado de modo a reproduzir, através de regras simples, as alterações e mudanças em grupos de seres vivos, tendo aplicações em diversas áreas da ciência.
As regras definidas são aplicadas a cada nova "geração"; assim, a partir de uma imagem em um tabuleiro bi-dimensional definida pelo jogador, percebem-se mudanças muitas vezes inesperadas e belas a cada nova geração, variando de padrões fixos a caóticos.
Regras O jogo da vida se passa em um arranjo bidimensional infinito de células que podem estar em um de dois estados, vivo ou morto. Cada célula interage com suas oito vizinhas, as células adjacentes horizontal, vertical e diagonalmente. O jogo evolui em unidades de tempo discretas chamadas de gerações. A cada nova geração, o estado do jogo é atualizado pela aplicação das seguintes regras:
Toda célula morta com exatamente três vizinhos vivos torna-se viva (nascimento). Toda célula viva com menos de dois vizinhos vivos morre por isolamento. Toda célula viva com mais de três vizinhos vivos morre por superpopulação. Toda célula viva com dois ou três vizinhos vivos permanece viva.
As regras são aplicadas simultaneamente em todas as células para chegar ao estado da próxima geração.
Origem Um dos problemas matemáticos mais famosos dos anos 40, do século XX, era o de achar uma máquina capaz de construir cópias de si mesma, que teve uma solução baseada em um autômato celular extremamente engenhoso e complicado inventado pelo renomado matemático John von Neumann. Conway inventou o Jogo da Vida (ou Game of Life) ao utilizar suas descobertas anteriores relacionadas com o problema de encontrar um grupo simétrico de esferas em 24 dimensões, proposto por John Leech para simplificar a solução de von Neumann.
O jogo fez sua primeira aparição na edição de Outubro de 1970 da Scientific American, na coluna de jogos matemáticos de Martin Gardner. De um ponto de vista teórico, ele é interessante, pois tem o poder de uma máquina de Turing universal: tudo pode ser computado através de algoritmos no Jogo da Vida de Conway.Berlekamp, E. R.; Conway, John Horton; Guy, R.K. (2001 2004). Winning Ways for your Mathematical Plays\\ (2nd ed.). A K Peters Ltd. ISBN 978-1-56881-130-7; ISBN 156881142X; ISBN 1568811438; ISBN 1568811446 Também era dito desde 1970 que foi destinado mais tempo de computação ao Jogo da Vida do que a qualquer outra atividade. Gardner escreveu: "O jogo fez Conway famoso instantaneamente, mas ele também abriu um novo campo na pesquisa matemática, o campo dos autômatos celulares... Por causa das analogias de Life com o aumento, redução e alteração de uma sociedade de organismos vivos, isto pertence a uma classe crescente que é chamada "jogos de simulação" - jogos que recriam processos do mundo-real."
Desde sua publicação, ele tem atraído muito interesse devido aos caminhos surpreendentes que pode tomar. Life é um exemplo de auto-organização. Ele é interessante para biólogos, matemáticos, estatísticos, economistas, filósofos e artistas por permitir a observação do modo como imagens complexas podem surgir de implementações de regras muito simples.
O Jogo da Vida tem um número de imagens reconhecidas que emergem de posições iniciais particulares. Antes da publicação, muitas imagens interessantes já haviam sido descobertas, incluindo o sempre envolvente R-pentomino (mais conhecido como "F-pentomino" fora do jogo), o auto propulsionado "glider", e várias "guns" (armas) que geravam um fluxo sem fim de novas imagens, todas aumentando o interesse no jogo. Sua popularidade foi ajudada pelo fato de ele ter vindo justo no momento em que uma nova geração de minicomputadores de baixo custo estavam sendo disponibilizados no mercado, significando que o jogo poderia ser rodado por horas nessa máquinas que não eram utilizadas de noite. Isto escondeu a popularidade posterior dos fractais gerados por computador. Para muitos aficcionados, Life era simplesmente um desafio de programação, um método divertido de gastar os ciclos da CPU. Para alguns, no entanto, Life tinha conotações mais filosóficas. Ele desenvolveu um culto através da década de 1970 e no meio da década de 1980; os desenvolvimentos atuais foram tão longe a ponto de criar emulações teóricas de sistemas de computadores com as regras de um tabuleiro de Life.
Descrição Este "jogo" é na realidade um jogo sem jogador, o que quer dizer que sua evolução é determinada pelo seu estado inicial, não necessitando de nenhuma entrada de jogadores humanos. Ele é jogado em um conjunto de células quadradas que seguem ao infinito em todas as direções. Cada célula tem oito "vizinhos", que são as células adjacentes, incluindo as diagonais. Cada célula pode estar em dois estados: "viva" ou "morta". (Também são usados os termos "ligado" e "desligado".) O estado do tabuleiro evolui e se modifica em pequenas passagens de tempo. Os estados de todas as células em um instante são considerados para calcular o estado de todas as células no instante seguinte. Todas as células são atualizadas simultaneamente. As transições dependem apenas do número de vizinhos vivos (ver as regras acima).
O Jogo A ideia básica do "jogo" é começar com uma configuração simples de células vivas (organismos) que são colocadas em um tabuleiro 2D de vários métodos. Isto constitui a primeira geração. As "leis genéticas" de Conway para nascimentos, mortes e sobrevivência (as quatro regras acima) são então aplicadas e a nova geração é então colocada de acordo. Geração a geração os "jogador(es)" observam as várias imagens que surgem.
A vida sempre segue De uma imagem inicial de células vivas no tabuleiro, percebe-se que, conforme passam as gerações, a população anda constantemente de modo não usual, algumas vezes belo e quase sempre inesperado, porém muda. Em muito poucos casos a sociedade eventualmente morre (todas as células se tornam células mortas), apesar de que isso pode não acontecer até que ocorram uma série de novas gerações. A maioria das imagens iniciais chegam a figuras estáveis - Conway chama-as de "vida parada" - que não podem mudar ou imagens que oscilam para sempre. Imagens sem simetria inicial tendem a se tornar simétricas. Uma vez que isto ocorre, a simetria não pode mais ser perdida, apesar de poder crescer em riqueza.
Conway originalmente supôs que nenhuma imagem poderia crescer ilimitadamente. Em outras palavras, qualquer configuração com um número finito de células não pode crescer além de um limite finito superior ao número de células do campo. Esta foi provavelmente a mais profunda e mais difícil questão colocada pelo jogo atualmente. Conway ofereceu um prêmio de $50 à primeira pessoa que pudesse provar a afirmação ou seu contrário antes do fim de 1970. Um caminho para provar seu contrário era ser capaz de descobrir imagens que continuassem adicionando contadores ao campo: Uma "gun" (uma configuração que constantemente atira objetos que se movimentam, como o "glider") ou um "puffer train" (uma configuração que se move mas deixa atrás uma trilha de "fumaça"). O prêmio foi ganho em novembro do mesmo ano por um time do MIT, a configuração inicial (mostrada no topo da página) cresce como um gun, emitindo seu primeiro glider na 40a geração. A gun emite então um novo glider a cada 30 gerações.
Exemplos de imagens direita|frame|A evolução e o movimento de um "glider". Existe uma série de diferentes imagens que podem ocorrer no Jogo da Vida, incluindo imagens paradas ("vidas paradas"), imagens repetitivas ("osciladores" - o conjunto de vidas paradas), e imagens que se movimentam através do tabuleiro ("naves espaciais"). Os exemplos mais simples dessas classes são mostrados abaixo, com as células vivas em preto, e as células mortas em branco.
Imagem:game of life block.png Imagem:game of life boat.png Imagem:game of life blinker.png Imagem:game of life toad.png Imagem:game of life glider.png Imagem:game of life lwss.png Bloco (block) Bote (boat) Piscador (blinker) Sapo (toad) Planador (glider) Espaçonave peso-leve (lightweight spaceship)
O "bloco" e o "bote" são vidas paradas, o "blinker" e o "sapo" são osciladores, e o "glider" e o "lightweight spaceship" ("LWSS") são naves espaciais que seguem seu caminho no tabuleiro conforme o tempo passa.
Imagens chamadas "Matusalens" podem evoluir por longos períodos de tempo antes de se repetir. "Diehard" é uma imagem que eventualmente desaparece após 130 gerações, ou passos. "Acorn" leva 5206 gerações para criar 13 gliders depois se estabiliza como vários osciladores.
Imagem:game of life diehard.png Imagem:game of life methuselah.png Diehard Acorn
Na aparição original do jogo em "Jogos Matemáticos", Conway ofereceu um prêmio em dinheiro para quem descobrisse qualquer imagem que crescesse indefinidamente. A primeira dessas foi encontrada por Bill Gosper em novembro de 1970. Ela incluía "guns (armas)", que eram estacionárias e atiravam gliders ou outras nave espaciais; "puffers", que se movem deixando atrás uma trilha de fumaça; e "rakes", que se movem e emitem naves espaciais. Gosper também descobriu depois uma imagem com uma taxa de crescimento quadrática, chamada de "breeder", que trabalhava deixando atrás uma trilha de guns. Desde então, uma série de construções complicadas têm sido feitas, incluindo portas lógicas de gliders, um somador, um gerador de números primos e uma unidade de célula que emula o Jogo da Vida em uma escala muito maior e a passos lentos.
O primeiro glider gun encontrado é ainda o menor conhecido:
centro|Glider Gun de Gosper
Posteriormente, foram encontradas imagens mais simples que tinham crescimento infinito. Todas as três imagens a seguir possuem crescimento infinito. As duas primeiras criam uma chave com um bloco, enquanto a terceira cria dois. A primeira tem apenas dez células vivas (o que se provou que é o mínimo). A segunda cabe em um quadrado de 5x5. A terceira possui apenas 1 célula de altura:
Imagem:game of life infinite1.png Imagem:game of life infinite2.png Imagem:game of life infinite3.png
É possível que gliders interajam com outros objetos de modos interessantes. Por exemplo, se dois gliders são atirados na direção de um bloco, o bloco irá se aproximar da fonte dos gliders. Se três gliders são atirados no mesmo lugar, o bloco irá se afastar. Esta "memória de bloco deslizante" pode ser usada para simular um contador. É possível construir portas lógicas AND, OR e NOT usando gliders. É possível construir uma imagem que aja como uma máquina de estado finito conectada a dois contadores. Isto possui o mesmo poder computacional de uma máquina de Turing universal (veja contador para a prova), Jogo da Vida é tão poderoso quanto qualquer computador com memória ilimitada: é o Turing completo. Além disso, uma imagem pode conter um conjunto de guns que se combina para construir novos objetos, incluindo cópias da imagem original. Um "construtor universal" pode ser construído que contenha um computador Turing completo, e que pode construir uma série de objetos complexos, incluindo mais cópias de si mesma. (Descrições destas construções são dadas em Winning Ways de Conway, Elwyn Berlekamp e Richard Guy.)
Algoritmos miniaturadaimagem|Algoritmo de acasalamento no Jogo da Vida Os primeiros resultados no Jogo da Vida foram obtidos sem o uso de computadores. As vidas paradas e os osciladores mais simples foram descobertos enquanto desenvolvendo várias configurações pequenas iniciais usando folhas de gráfico, quadros negros ou tabuleiros e peças. Durante as pesquisas iniciais, Conway descobriu que o R-pentomino não se estabiliza em um número pequeno de gerações.