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^(inglês) , formiga^(português) 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".^[1] 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^(inglês) é o mesmo que girar^(português)).^[2]^[3]

Aparentemente de forma independente,^[4] 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.^[5] Rudy Rucker relata a seguinte história:

Dewdney relatou que, procurando por um nome para as criaturas de Turk, ele pensou, "Bem, elas são máquinas de Turing estudadas por Turk, então elas podem ser "tur-alguma coisa". E elas são como pequenos insetos, ou ácaros (mites^(inglês)), então vou chamá-las tur-mites! E isso soa como termites!" Com a gentil permissão de Turk e Dewdney, eu vou deixar de fora o hífen e chamá-las de turmites.
— Rudy Rucker, Artificial Life Lab^[4]

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
		0			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.^[3] 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.^[6]

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.)

Ver também

Referências

↑ Langton, Chris G. (1986). «Studying artificial life with cellular automata». Physica D: Nonlinear Phenomena. 22: 120–149. doi:10.1016/0167-2789(86)90237-X
↑ Brady, Allen H. (1988). «The Busy Beaver Game and the Meaning of Life». In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey. [S.l.]: Springer-Verlag. ISBN 0-19-853741-7
↑ ^a ^b Brady, Allen H. (1995). «The Busy Beaver Game and the Meaning of Life». In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey 2nd ed. [S.l.]: Springer-Verlag. pp. 237–254. ISBN 3-211-82637-8
↑ ^a ^b Rucker, Rudy. «Artificial Life Lab». Consultado em 16 de outubro de 2009. Arquivado do original em 10 de junho de 2011
↑ Dewdney, A. K. (1989). «Two-dimensional Turing machines and Turmites make tracks on a plane». Scientific American: 180–183
↑ Pegg, Jr., Ed. «Math Puzzle». Consultado em 15 de outubro de 2009

Ligações externas

[1] Langton, Chris G. (1986). «Studying artificial life with cellular automata». Physica D: Nonlinear Phenomena. 22: 120–149. doi:10.1016/0167-2789(86)90237-X

[2] Brady, Allen H. (1988). «The Busy Beaver Game and the Meaning of Life». In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey. [S.l.]: Springer-Verlag. ISBN 0-19-853741-7

[Brady95-3] Brady, Allen H. (1995). «The Busy Beaver Game and the Meaning of Life». In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey 2nd ed. [S.l.]: Springer-Verlag. pp. 237–254. ISBN 3-211-82637-8

[rucker-4] Rucker, Rudy. «Artificial Life Lab». Consultado em 16 de outubro de 2009. Arquivado do original em 10 de junho de 2011

[5] Dewdney, A. K. (1989). «Two-dimensional Turing machines and Turmites make tracks on a plane». Scientific American: 180–183

[6] Pegg, Jr., Ed. «Math Puzzle». Consultado em 15 de outubro de 2009

[1]

[2]

[3]

[4]

[5]

[6]