Saltar para o conteúdo

Turmite

Origem: Wikipédia, a enciclopédia livre.
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 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
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]

  • Alguns exemplos de turmites 2-estados 2-cores em uma grade quadrada, todas iniciando com uma configuração vazia:
  • Crescimento em espiral.
    Crescimento em espiral.
  • Produção de "estrada" (um caminho regular) depois de um período de crescimento caótico.
    Produção de "estrada" (um caminho regular) depois de um período de crescimento caótico.
  • Crescimento caótico com uma textura diferenciada.
    Crescimento caótico com uma textura diferenciada.
  • Crescimento com uma textura distinta dentro de um quadro de expansão.
    Crescimento com uma textura distinta dentro de um quadro de expansão.
  • Construindo uma espiral de Fibonacci.
    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[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.)

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

Referências

  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 
  3. ↑ 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 
  4. ↑ a b 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 

Ligações externas[editar | editar código-fonte]

Obtida de "https://pt.wikipedia.org/w/index.php?title=Turmite&oldid=67163722"