O ‘jogo da vida’ da matemática revela padrões de repetição há muito procurados | Revista Quanta

Em 1969, o matemático britânico John Conway elaborou um conjunto de regras simples e sedutoras para criar comportamentos complexos. Seu Jogo da Vida, muitas vezes referido simplesmente como Vida, se desenrola em uma grade quadrada infinita de células. Cada célula pode estar “viva” ou “morta”. A grade evolui ao longo de uma série de turnos (ou “gerações”), com o destino de cada célula determinado pelas oito células que a cercam. As regras são as seguintes:

1. Nascimento: Uma célula morta com exatamente três vizinhos vivos torna-se viva.
2. Sobrevivência: Uma célula viva com dois ou três vizinhos vivos permanece viva.
3. Morte: Uma célula viva com menos de dois ou mais de três vizinhos vivos morre.

Estas regras simples criam um conjunto surpreendentemente diversificado de padrões, ou “formas de vida”, que evoluem a partir das muitas configurações iniciais possíveis da rede. Os amantes do jogo registraram e taxonomizaram esses padrões em uma escala cada vez maior. catálogo online. Conway descobriu um padrão chamado pisca-pisca, que oscila entre dois estados.

No ano seguinte, ele encontrou um padrão muito mais complicado chamado pulsar, que oscila entre três estados diferentes.

Logo após a descoberta dos osciladores, os primeiros exploradores do jogo se perguntaram se existiam osciladores de todos os períodos. “No início, víamos apenas os períodos 1, 2, 3, 4 e 15”, disse o programador de computador e matemático Bill Gosper, que iria descobrir 17 novos osciladores diferentes nas décadas seguintes. Os osciladores do período 15 (mostrados abaixo) surgiram com uma frequência surpreendente em pesquisas aleatórias.

Surpresas espreitavam aqueles que desejavam encontrá-las. “Depois de horas e dias de exibição, o período 5 parecia impossível”, disse Gosper. Então, em 1971, dois anos após a invenção do jogo, um foi encontrado. A busca por novos osciladores tornou-se o foco principal do jogo, uma busca reforçada pelo advento da tecnologia computacional. Relatos de buscas secretas realizadas em computadores de escritório tornaram-se a pedra angular do folclore do jogo. “A quantidade de tempo de computador roubado de mainframes corporativos e universitários foi impressionante”, disse Gosper.

Ao longo da década de 1970, matemáticos e amadores preencheram os outros períodos curtos e encontraram alguns períodos mais longos. Eventualmente, os matemáticos descobriram uma maneira sistemática de construir osciladores de longo período. Mas os osciladores com períodos entre 15 e 43 revelaram-se difíceis de encontrar. “As pessoas vêm tentando descobrir o meio há anos”, disse Maia Karpovich, estudante de pós-graduação da Universidade de Maryland. Preencher as lacunas forçou os pesquisadores a imaginar uma série de novas técnicas que ultrapassassem os limites do que se pensava ser possível com os autômatos celulares, como os matemáticos chamam de grades em evolução como a Vida.

Agora Karpovich e seis coautores anunciaram em um Pré-impressão de dezembro que encontraram os dois últimos períodos em falta: 19 e 41. Com essas lacunas preenchidas, a Vida é agora conhecida por ser “omniperiódica” – nomeie um número inteiro positivo, e existe um padrão que se repete após tantos passos.

A crescente comunidade dedicada ao estudo da Vida, que inclui muitos matemáticos pesquisadores, mas também muitos amadores, encontrou não apenas osciladores, mas todos os tipos de novos padrões. Eles encontraram padrões que viajam pela grade, chamados de naves espaciais, e padrões que constroem outros padrões: armas, construtores e criadores. Eles encontraram padrões que computam números primos e até padrões que podem executar algoritmos arbitrariamente complicados.

Osciladores com períodos menores que 15 podem ser encontrados manualmente ou com algoritmos rudimentares que procuram osciladores uma célula por vez. Mas à medida que o período aumenta, aumenta também a complexidade, tornando as pesquisas de força bruta muito menos eficazes. “Para períodos pequenos, você pode pesquisar diretamente”, disse Matthias Merzenich, coautor do novo artigo que descobriu o primeiro oscilador de período 31 em 2010. “Mas você realmente não pode ir além disso. Você não pode simplesmente escolher um período e procurá-lo.” (Merzenich obteve seu doutorado em matemática pela Oregon State University em 2021, mas atualmente trabalha em uma fazenda.)

Em 1996, David Buckingham, um consultor de informática autônomo canadense e entusiasta da vida que procurava padrões desde o final dos anos 1970, mostrou que era possível construir osciladores de período 61 e superior, enviando um padrão ao redor de uma trilha fechada em um loop infinito. . Ao controlar o comprimento do loop – e o tempo que o padrão levou para completar uma viagem de ida e volta – Buckingham descobriu que poderia tornar o período tão grande quanto quisesse. “É química sem cheiros estranhos ou vidros quebrados”, disse ele. “Como construir compostos e depois explorar as interações entre eles.” Isto significou que, de uma só vez, ele descobriu uma forma de construir osciladores de períodos arbitrariamente longos, desde que fossem superiores a 61.

Houve uma série de resultados em meados da década de 1990, quando muitos dos osciladores ausentes entre 15 e 61 foram descobertos através de combinações criativas de osciladores conhecidos, que receberam uma série de nomes coloridos. Os fornecedores foram combinados com semáforos, os vulcões cuspiram faíscas e os comedores comeram planadores.

Na virada do século 21, apenas uma dúzia de períodos ainda estavam pendentes. “Parecia muito possível resolver este problema”, disse Merzenich. Em 2013, uma nova descoberta chamada loop de Snark melhorou a técnica de Buckingham de 1996 e reduziu o limite acima do qual era fácil construir osciladores de 61 para 43. Isso deixou apenas cinco períodos faltantes. Mais um foi descoberto em 2019 e mais dois em 2022, restando apenas 19 e 41 – ambos primos. “Os números primos são mais difíceis porque não é possível usar osciladores de pequeno período para construí-los”, disse Merzenich.

Mitchell Riley, pesquisador de pós-doutorado na Universidade de Nova York em Abu Dhabi e outro coautor do novo artigo, há muito tempo fica intrigado com um tipo de oscilador chamado incômodo. “A maneira como os incômodos funcionam é que você tem um padrão ativo no meio e algumas coisas estáveis ​​do lado de fora que reagem a ele”, explicou Riley. O material estável, chamado catalisador, existe para empurrar o padrão ativo de volta ao seu estado original.

Projetá-los é difícil. “Todos esses padrões são incrivelmente frágeis”, disse Riley. “Se você colocar um único ponto fora do lugar, ele geralmente explode.”

Riley criou um programa chamado Barrister para procurar novos catalisadores. “O que procuramos são naturezas-mortas robustas. A questão é que queremos que eles interajam com o que está acontecendo no meio e depois se recuperem”, disse Riley.

Riley alimentou catalisadores que Barrister encontrou em outro programa de busca que os combinou com padrões ativos. Isso levou principalmente a falhas, disse ele. “É bastante raro que um desses catalisadores sobreviva à interação. Não há garantia de sucesso. Você meio que cruza os dedos e torce para tirar a sorte grande. Parece um pouco com um jogo de azar.”

Eventualmente, sua aposta valeu a pena. Depois de alguns quase acidentes – e uma modificação no código que expandiu a busca para incluir padrões simétricos – ele encontrou uma interação catalisadora que poderia sustentar um oscilador de período 19. “As pessoas estavam tentando todos os tipos de pesquisas realmente complicadas com muitos catalisadores e muitas coisas ativas raras no meio, mas tudo o que era necessário era encontrar esse novo catalisador robusto”, disse Riley.

O último período faltante, 41, foi encontrado por Nicolo Brown, outro coautor, que ainda cursa matemática na Universidade da Califórnia, em Santa Cruz. Brown usou planadores como catalisadores, uma ideia proposta pela primeira vez por Merzenich.

“Descobrimos muitos comportamentos profundos nos últimos 10 anos”, disse Karpovich. “Todo mundo está comemorando por uma semana – e depois passando para outras coisas. Há tantos outros problemas para resolver.” Os osciladores de um determinado período podem ser reduzidos? Podem ser encontrados osciladores nos quais cada célula oscila? As armas podem ser fabricadas com períodos específicos? As naves espaciais podem viajar a velocidades específicas?

Como disse Buckingham: “É como ser uma criança em uma loja de brinquedos infinita”.