# Turmite

Em ciência da computação, uma turmite é uma Máquina de Turing que tem uma orientação, bem como um estado atual e uma fita que consiste de uma grade bidimensional infinita de células. Os termos ant , formiga e vant também são usados. Formiga de Langton é um tipo bem conhecido de turmite definida sobre as células de uma grade quadrada. Paterson's worms é um tipo de turmite definida nos limites de uma grade isométrica.
Tem sido demonstrado que turmites em geral, são exatamente equivalentes em poder a máquinas unidimensionais Turing com uma fita infinita, pois uma pode simular a outra.

## História

As Formigas de Langton foram inventadas em 1986 e declaradas "equivalentes a máquinas de Turing". Independentemente, em 1988, Allen H. Brady considerou a ideia de máquinas de Turing bidimensionais com uma orientação e chamou-as "máquinas TurNing" (turn é o mesmo que girar).
Aparentemente de forma independente, Greg Turk investigou o mesmo tipo de sistema e escreveu a A. K. Dewdney sobre eles. A. K. Dewdney nomeou-os "tur-mites" em sua coluna "Computer Recreations" na Scientific American em 1989. Rudy Rucker relata a seguinte história:

## Turmites relativas vs. absolutas

Turmites podem ser categorizadas como sendo relativas ou absolutas. Turmites relativas, alternativamente conhecidas como 'máquinas Turning', tem uma orientação interna. A Formiga de Langton é um exemplo. Turmites relativas são, por definição, isotrópicas; girar a turmite não afeta o seu resultado. Turmites relativas são chamadas assim porque as instruções são codificadas relativas à orientação atual, equivalente a usar as palavras 'esquerda' ou 'para trás'. Turmites absolutas, por comparação, codifica suas direções em termos absolutos: uma instrução particular pode direcionar a turmite a se mover para 'Norte'. Turmites absolutas são bidimensionais análogas às máquinas de Turing convencionais, então são ocasionalmente referidas simplesmente como "Máquinas de Turing Bidimensionais". O restante deste artigo está abordando o caso relativo.

## Especificação

A seguinte especificação é para turmites sobre uma grade bidimensional quadrada, o tipo mais estudado de turmite. Turmites sobre outras grades podem ser especificadas de um modo semelhante.
Tal como acontece com a Formiga de Langton, turmites realizam as seguintes operações cada iteração:
* Girar no local (por algum múltiplo de 90°)
* Mudar a cor do quadrado
* Avançar um quadrado
Tal como acontece com as máquinas de Turing, as ações são especificadas por uma tabela de transição de estado listando o estado interno atual e a cor da célula que está atualmente ativa. Por exemplo, a turmite exibida na imagem do topo desta página é especificada pela tabela seguinte:
| | | Cor atual | Cor atual | Cor atual | Cor atual | Cor atual | Cor atual |
| | | 0 | 0 | 0 | 1 | 1 | 1 |
| | | Escrever cor | Girar | Próximo estado | Escrever cor | Girar | Próximo estado |
| Estado atual | 0 | 1 | D | 0 | 1 | D | 1 |
| Estado atual | 1 | 0 | N | 0 | 0 | N | 1 |
A direção do giro pode ser E (90° esquerda), D (90° direita), N (sem girar) ou U (180°).

## Exemplos

* Alguns exemplos de turmites 2-estados 2-cores em uma grade quadrada, todas iniciando com uma configuração vazia:
* Crescimento em espiral.
* Produção de "estrada" (um caminho regular) depois de um período de crescimento caótico.
* Crescimento caótico com uma textura diferenciada.
* Crescimento com uma textura distinta dentro de um quadro de expansão.
* Construindo uma espiral de Fibonacci.
Iniciando com uma grade vazia ou com outras configurações, os comportamentos mais comumente observados são o crescimento caótico, o crescimento em espiral e a construção de "estradas". Raros exemplos tornam-se periódicos após um número de passos.

## Turmites e o jogo Busy Beaver

Allen H. Brady pesquisou por turmites com parada (equivalente a busy beavers) e encontrou uma máquina de 2-estados 2-cores que imprimiu 37 uns (1) antes de parar, e outra que levou 121 passos antes de parar. Ele também considerou turmites que se movem numa grade triangular, encontrando outros busy beavers.
Ed Pegg, Jr. considerou outras abordagens para o jogo Busy Beaver. Ele sugeriu que podem girar, por exemplo, para esquerda e direita ao mesmo tempo, se dividindo em dois. Turmites que posteriormente se encontram para aniquilar umas as outras. Nesse sistema, um Busy Beaver está a partir de um padrão inicial de uma simples turmite dura mais tempo antes de todas as turmites se aniquilarem.

## Outras grades

Após o trabalho inicial de Allen H. Brady sobre turmites numa grade triangular, mosaicos hexagonais também tem sido explorados. Muito deste trabalho é devido a Tim Hutton, e seus resultados estão no Rule Table Repository. Ele também considerou turmites em três dimensões e colheu alguns resultados preliminares. Allen H. Brady e Tim Hutton também têm investigado turmites unidimensionais relativas ao inteiro lattice, que Brady nomeou flippers. (Turmites unidimensionais absolutas são evidentemente conhecidas como máquinas de Turing.)