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
[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:
- 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 |
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]-
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
[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
- ↑ 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
[editar | editar código-fonte]- Página web demonstrando várias turmites
- Jogos Matemáticos: Máquinas de Turing 2D, em MAA Online
- Jogos Matemáticos: Paterson's Worms Revisitado, em MAA Online
- Turmite, em MathWorld.
- Script Golly para geração de turmites arbitrárias
- Movimento relativo e absoluto de Turmites and Busy Beavers em grades quadradas, cúbicas triangulares e hexagonais