Turmite

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Uma turmite 2-estados 2-cores numa grade quadrada. Iniciando com um grid quadrado, depois de 8342 passos a turmite (o pixel vermelho) exibiu um movimento com fases caóticas e regulares.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:

  1. Girar no local (por algum múltiplo de 90°)
  2. Mudar a cor do quadrado
  3. 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 image do topo dessa 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
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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Langton, Chris G.. . "Studying artificial life with cellular automata" 22: 120–149. DOI:10.1016/0167-2789(86)90237-X.
  2. In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey. [S.l.: s.n.]. ISBN 0-19-853741-7
  3. a b Brady, Allen H.. In: Rolf Herken. The Universal Turing Machine: A Half-Century Survey. [S.l.]: Springer-Verlag. ISBN 3-211-82637-8
  4. a b Rucker, Rudy. Artificial Life Lab. Visitado em October 16, 2009.
  5. Dewdney, A. K.. (Setembro 1989). "Two-dimensional Turing machines and Turmites make tracks on a plane". Scientific American: 180–183.
  6. Pegg, Jr., Ed. Math Puzzle. Visitado em 15 October 2009.

Links externos[editar | editar código-fonte]