Turmita

En informática , una turmita es una máquina de Turing que posee una orientación, además de un estado actual, y una "cinta" que consiste en una cuadrícula bidimensional infinita de celdas. También se utilizan los términos hormiga y vant . La hormiga de Langton es un tipo conocido de turmita definida en las celdas de una cuadrícula cuadrada. Los gusanos de Paterson son un tipo de turmita definida en los bordes de un teselado triangular .

Se ha demostrado que las turmitas, en general, son exactamente equivalentes en potencia a las máquinas de Turing unidimensionales con una cinta infinita, ya que ambas pueden simular a la otra.

Las hormigas de Langton fueron inventadas en 1986 y declaradas "equivalentes a las máquinas de Turing". ^{[ 1 ]} De forma independiente, en 1988, Allen H. Brady consideró la idea de máquinas de Turing bidimensionales con una orientación y las denominó "máquinas de Turing". ^{[ 2 ] [ 3 ]}

Aparentemente de forma independiente a ambos, ^{[ 4 ]} Greg Turk investigó el mismo tipo de sistema y le escribió a AK Dewdney sobre ellos. AK Dewdney los denominó "tur-mites" en su columna "Recreaciones por computadora" en Scientific American en 1989. ^{[ 5 ]} Rudy Rucker relata la historia de la siguiente manera:

Dewdney cuenta que, buscando un nombre para las criaturas de Turk, pensó: «Bueno, son máquinas de Turing estudiadas por Turk, así que deberían ser algo parecido a "tur-algo". Y son como pequeños insectos, o ácaros, ¡así que las llamaré tur-mitas! ¡Y suena como termitas!». Con el amable permiso de Turk y Dewdney, voy a omitir el guion y las llamaré turmitas.

Las turmitas se pueden clasificar en relativas o absolutas . Las turmitas relativas, también conocidas como "máquinas de giro", tienen una orientación interna. La hormiga de Langton es un ejemplo de ello. Por definición, las turmitas relativas son isotrópicas ; girar la turmita no afecta su resultado. Se denominan así porque las direcciones se codifican en relación con la orientación actual, equivalente a usar las palabras "izquierda" o "atrás". Las turmitas absolutas, en cambio, codifican sus direcciones en términos absolutos: una instrucción particular puede indicar a la turmita que se mueva "hacia el norte". Las turmitas absolutas son análogos bidimensionales de las máquinas de Turing convencionales, por lo que a veces se las denomina simplemente "máquinas de Turing bidimensionales". El resto de este artículo se centra en el caso relativo.

La siguiente especificación se refiere específicamente a las turmitas en una cuadrícula cuadrada bidimensional, el tipo de turmita más estudiado. Las turmitas en otras cuadrículas pueden especificarse de manera similar.

Al igual que la hormiga de Langton, las hormigas turmitas realizan las siguientes operaciones en cada paso de tiempo:

1. girar sobre el mismo punto (en algún múltiplo de 90°)
2. cambia el color del cuadrado
3. avanzar una casilla.

Al igual que con las máquinas de Turing, las acciones se especifican mediante una tabla de transición de estados que indica el estado interno actual del turmite y el color de la celda en la que se encuentra. Por ejemplo, el turmite que se muestra en la imagen superior de esta página se especifica mediante la siguiente tabla:

La dirección para girar es una de las siguientes: L (90° a la izquierda), R (90° a la derecha), N (sin girar) y U ( giro en U de 180° ).

• Ejemplos de turmites de dos estados y dos colores en una cuadrícula cuadrada , todos partiendo de una configuración vacía:
• 
  Crecimiento en espiral
• 
  Construcción de una autopista tras un período de crecimiento caótico.
• 
  Crecimiento caótico con una textura distintiva
• 
  Crecimiento con una textura distintiva dentro de un marco en expansión
• 
  Construcción de una espiral de Fibonacci
• 
  Construyendo un diamante en crecimiento

• Ejemplos de turmites con más estados y colores y en cuadrículas no cuadradas:
• 
  Turmita de tres estados y dos colores que produce un patrón fractal similar a un copo de nieve.
• 
  Turmita de tres colores y tres estados sobre una cuadrícula hexagonal , que crece caóticamente con una textura distintiva antes de quedar atrapada en un bucle periódico después de aproximadamente 194150 pasos.

Partiendo de una cuadrícula vacía u otras configuraciones, los comportamientos más comunes son el crecimiento caótico, el crecimiento en espiral y la construcción de "autopistas". En raras ocasiones, el comportamiento se vuelve periódico tras un cierto número de pasos.

Allen H. Brady buscó máquinas de impresión de dos estados y dos colores que imprimían 37 unos antes de detenerse, y otra que tardaba 121 pasos en detenerse. ^{[ 3 ]} También consideró máquinas de impresión que se mueven en una cuadrícula triangular , encontrando varios castores ocupados también en este caso.

Ed Pegg, Jr. consideró otro enfoque para el juego del castor ocupado. Sugirió turmites que pueden girar, por ejemplo, tanto a la izquierda como a la derecha, dividiéndose en dos. Los turmites que luego se encuentran se aniquilan entre sí. En este sistema, un castor ocupado es aquel que, partiendo de un patrón inicial de un solo turmite, dura más tiempo antes de que todos los turmites se aniquilen entre sí. ^{[ 6 ]}

Tras el trabajo inicial de Allen H. Brady sobre turmites en una cuadrícula triangular, también se han explorado los teselados hexagonales . Gran parte de este trabajo se debe a Tim Hutton, cuyos resultados se encuentran en el Repositorio de Tablas de Reglas. También ha estudiado los turmites en tres dimensiones y ha recopilado algunos resultados preliminares. Allen H. Brady y Tim Hutton también han investigado los turmites relativos unidimensionales en la red entera , a los que Brady denominó flippers . (Los turmites absolutos unidimensionales se conocen simplemente como máquinas de Turing).

• Autómata celular : modelo discreto de computación. 
• La hormiga de Langton : una máquina de Turing bidimensional con comportamiento emergente. 
• Gusanos de Paterson : familia de autómatas celulares para modelar el comportamiento alimentario. 

• "Página web que muestra varias turmitas" . Archivada del original el 21/12/2013.
• Pegg Jr., Ed. (7 de junio de 2004). "Juegos matemáticos: máquinas de Turing 2D" . MAA Online. Archivado del original el 16 de mayo de 2013.
• Pegg Jr., Ed. (27 de octubre de 2003). "Juegos matemáticos: Una revisión de Los gusanos de Paterson" . MAA Online. Archivado del original el 23 de marzo de 2004.
• Turmite , en MathWorld .
• Script de Golly para generar turmites arbitrarios
• Turmites y Busy Beavers con movimiento absoluto y relativo en cuadrículas cuadradas, cúbicas, triangulares y hexagonales.