Vermes de Paterson

Os vermes de Paterson são uma família de autômatos celulares criados em 1971 por Mike Paterson e John Horton Conway para modelar o comportamento e os padrões de alimentação de determinados vermes pré-históricos. No modelo, um verme se move entre pontos em uma grade triangular ao longo de segmentos de linha, representando o alimento. Suas voltas são determinadas pela configuração de segmentos de linha comidos e não comidos adjacentes ao ponto em que o verme se encontra no momento. Apesar de ser regido por regras simples, o comportamento dos vermes pode ser extremamente complexo, e o destino de uma variante ainda é desconhecido.

Os vermes foram estudados no início da década de 1970 por Paterson, Conway e Michael Beeler, descritos por Beeler em junho de 1973, e apresentados em novembro de 1973 na coluna “Mathematical Games” de Martin Gardner na Scientific American.

O jogo Worms? [en] da Electronic Arts, de 1983, é uma implementação interativa dos vermes de Paterson, em que cada vez que um verme precisa girar de uma forma para a qual não tem uma regra, ele para e permite que o usuário escolha uma direção, o que define a regra para aquele verme.

História

Rastros de vermes fossilizados.

Os vermes de Paterson são uma tentativa de simular o comportamento dos vermes pré-históricos. Essas criaturas se alimentavam de sedimentos no fundo de lagoas e evitavam refazer os caminhos que já haviam percorrido porque o alimento seria escasso ali, mas, como o alimento ocorria em manchas, era do interesse da minhoca ficar perto das trilhas anteriores. Espécies diferentes de vermes tinham regras inatas diferentes em relação à proximidade dos caminhos percorridos, quando virar e qual a inclinação da curva a ser feita. Em 1969, Raup e Seilacher criaram simulações de computador das trilhas de vermes fossilizados, e essas simulações inspiraram Paterson e Conway a desenvolver um conjunto simples de regras para estudar vermes idealizados em grades regulares.

O modelo original de Conway era um verme em uma grade ortogonal, mas isso produziu apenas três espécies diferentes de vermes, todos com comportamento desinteressante. Paterson considerou vermes em uma grade triangular. Os vermes de Paterson foram descritos por Beeler em um memorando de IA do Instituto de Tecnologia de Massachusetts (#[1]) e foram apresentados em novembro de 1973 na coluna “Mathematical Games” de Martin Gardner na Scientific American, e posteriormente reimpressos em Gardner 1986. Essas simulações diferiam, em termos de abordagem, de outros autômatos celulares desenvolvidos na mesma época, que se concentravam nas células e nas relações entre elas. Modelos simples de computador como esses são muito abstratos para descrever com precisão o comportamento das criaturas reais, mas demonstram que mesmo regras muito simples podem dar origem a padrões que se assemelham a seus rastros.

Regras

O verme começa em algum ponto de uma grade triangular infinita. Ele começa a se mover ao longo de uma das seis linhas de grade que se encontram em cada ponto e, após percorrer uma unidade de distância, chega a um novo ponto. O verme decide então, com base na distribuição das linhas de grade percorridas e não percorridas, a direção que tomará. As direções são relativas ao ponto de vista do verme. Se ele não tiver encontrado essa distribuição exata antes, poderá sair por qualquer linha de grade não percorrida. A partir de então, se ele encontrar essa distribuição novamente, deverá se mover da mesma forma. Se não houver linhas de grade não atravessadas disponíveis, o verme morre e a simulação termina.

Discussão

Há muitos tipos de vermes, dependendo da direção para a qual eles se voltam ao encontrar um novo tipo de interseção. As diferentes variedades de vermes podem ser classificadas sistematicamente atribuindo um número a cada direção e listando a escolha feita toda vez que um novo tipo de interseção é encontrado.

As seis direções são numeradas da seguinte forma:

Portanto, a direção 0 indica que a minhoca continua a se deslocar em linha reta, a direção 1 indica que a minhoca fará uma curva à direita de 60° e o mesmo ocorre com as outras direções. O verme não pode viajar na direção 3 porque essa é a linha de grade que acabou de atravessar. Assim, um verme com a regra {1,0,5,1} decide viajar na direção 1 na primeira vez que tiver de fazer uma escolha, na direção 0 na próxima vez que tiver de fazer uma escolha e assim por diante. Se houver apenas uma linha de grade disponível, o verme não terá outra opção a não ser usá-la, e isso geralmente não é listado explicitamente.

O verme de Paterson com a regra { 2, 0, 0 }

Um verme cujo conjunto de regras começa com 0 continua em uma linha reta para sempre. Esse é um caso trivial, portanto, normalmente estipula-se que o verme deve se virar quando encontrar um ponto com apenas linhas de grade não consumidas. Além disso, para evitar duplicatas simétricas de imagens espelhadas, a primeira curva do verme deve ser à direita. Um verme morre se retornar à sua origem uma terceira vez, pois não há mais bordas não percorridas disponíveis. Somente a origem pode ser letal para o verme.

Há 1.296 combinações possíveis de regras do verme. Isso pode ser visto pelo seguinte argumento:

1. Se o verme encontrar um nó sem segmentos comidos, além daquele que acabou de comer, ele poderá fazer uma curva acentuada ou uma curva suave. Essa é a situação mostrada na figura acima. Como a escolha inicial de esquerda ou direita produz combinações que são simplesmente espelhos uma da outra, elas não são efetivamente diferentes.
2. Se ele encontrar um nó com um segmento comido, ele poderá sair por qualquer um dos quatro restantes. Somente o primeiro retorno do verme à origem tem esse caráter.
3. Para dois segmentos comidos, a localização dos segmentos comidos é importante. O único tipo de interseção de dois segmentos que pode existir é a produzida pela primeira regra, para a qual há quatro direções de aproximação distintas, cada uma das quais oferece uma opção de três direções de partida. Isso permite 81 alternativas diferentes na escolha de regras.
4. Se o verme retornar à origem, ele encontrará três segmentos comidos e deverá escolher entre os dois segmentos restantes não comidos, independentemente de sua distribuição.
5. Para quatro segmentos comidos, resta apenas um segmento não comido e o verme deve pegá-lo.

Portanto, há 2×4×81×2x1=1.296 combinações diferentes de regras. Muitas delas são duplicatas espelhadas de outras, e outras morrem antes de ter que fazer todas as escolhas em seu conjunto de regras, deixando 411 espécies distintas (412 se o verme infinito em linha reta for incluído). 336 dessas espécies acabam morrendo. 73 padrões apresentam comportamento infinito, ou seja, eles se estabelecem em um padrão de repetição que não retorna à origem. Acredita-se fortemente que outros dois sejam infinitos e um permanece sem solução. Onze das regras apresentam um comportamento complicado. Elas não morrem mesmo depois de muitos bilhões de iterações, nem adotam um padrão obviamente infinito. Seu destino era desconhecido até 2003, quando Benjamin Chaffin desenvolveu novos métodos para resolvê-las. Após muitas horas de trabalho com o computador, nove das onze regras foram resolvidas, deixando os vermes com as regras {1,0,4,2,0,2,0} e {1,0,4,2,0,1,5}. A primeira delas foi resolvida por Tomas Rokicki, que determinou que ela para após 57 trilhões (5,7×1013) de passos de tempo, deixando apenas {1,0,4,2,0,1,5} sem solução. De acordo com Rokicki, o verme continua ativo após 5,2×1019 passos de tempo. Ele usou um algoritmo baseado no Hashlife de Bill Gosper para simular os vermes em velocidades extraordinárias. Esse comportamento é consideravelmente mais complexo do que o verme de grade retangular relacionado, que tem um caminho mais longo de apenas 16 segmentos.

É possível que duas espécies diferentes de vermes produzam o mesmo caminho, embora não necessariamente o percorram na mesma ordem. O caminho mais comum é também o mais curto: o símbolo do teste MOT de sete pontos/abrigo nuclear. Um exemplo desse caminho é mostrado na figura animada acima. No total, há 299 caminhos diferentes, e 209 deles são produzidos por apenas uma espécie.

Ver também

• Algoritmo do castor - Máquina de Turing de execução mais longa de um determinado tamanho
• Formiga de Langton - Máquina de Turing bidimensional com comportamento emergente
• Máquina de Turing - Modelo de computação que define uma máquina abstrata
• Turritella terebra - Máquina de Turing em uma grade bidimensional

Ligações externas

• Página dos vermes de Rokicki (em inglês)
• Página dos vermes de Sven (em inglês)