En ciencias de la computación , una turmita es una máquina de Turing que tiene 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 bien conocido de turmita definido en las celdas de una cuadrícula cuadrada. Los gusanos de Paterson son un tipo de turmita definido en los bordes de una cuadrícula isométrica .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/0/0c/Turmite-120121010011-8342.png)
Se ha demostrado que los turmitas en general son exactamente equivalentes en potencia a las máquinas de Turing unidimensionales con una cinta infinita, ya que cualquiera puede simular a la otra.
Historia
Las hormigas de Langton fueron inventadas en 1986 y declaradas "equivalentes a las máquinas de Turing". [1] Independientemente, en 1988, Allen H. Brady consideró la idea de máquinas de Turing bidimensionales con una orientación y las llamó "máquinas de torneado". [2] [3]
Aparentemente independientemente de ambos, [4] Greg Turk investigó el mismo tipo de sistema y escribió a AK Dewdney sobre ellos. AK Dewdney los nombró "tur-ácaros" en su columna "Recreaciones informáticas" en Scientific American en 1989. [5] Rudy Rucker relata la historia de la siguiente manera:
Dewdney informa que, buscando un nombre para las criaturas de Turk, pensó: "Bueno, son máquinas de Turing estudiadas por Turk, por lo que deberían ser tur-algo. Y son como pequeños insectos o ácaros, así que yo" ¡Los llamaré tur-ácaros! ¡Y eso suena a termitas! " Con el amable permiso de Turk y Dewdney, omitiré el guión y los llamaré turmitas.
- Rudy Rucker, Laboratorio de vida artificial [4]
Turmitas relativas vs absolutas
Los turmitas se pueden clasificar como relativos o absolutos . Las turmitas relativas, también conocidas como "Tornos", tienen una orientación interna. La hormiga de Langton es un ejemplo. Los turmitas relativos son, por definición, isotrópicos ; girar la turmita no afecta su resultado. Los turmitas relativos se denominan así porque las direcciones están codificadas en relación con la orientación actual, equivalente a usar las palabras "izquierda" o "al revés". Los turmitas absolutos, en comparación, codifican sus direcciones en términos absolutos: una instrucción particular puede dirigir a los turmitas a moverse "hacia el norte". Los turmitas absolutos son análogos bidimensionales de las máquinas de Turing convencionales, por lo que ocasionalmente se denominan simplemente "máquinas de Turing bidimensionales". El resto de este artículo se ocupa del caso relativo.
Especificación
La siguiente especificación es específica para turmitas en una cuadrícula cuadrada bidimensional, el tipo de turmitas más estudiado. Los turmitas en otras rejillas se pueden especificar de manera similar.
Al igual que con la hormiga de Langton, los turmitas realizan las siguientes operaciones en cada paso de tiempo:
- girar en el lugar (en un múltiplo de 90 °)
- cambiar el color del cuadrado
- avanzar un cuadrado.
Al igual que con las máquinas de Turing, las acciones se especifican mediante una tabla de transición de estado que enumera el estado interno actual de la turmita y el color de la celda en la que se encuentra actualmente. Por ejemplo, la turmita que se muestra en la imagen en la parte superior de esta página se especifica en la siguiente tabla:
Color actual | |||||||
---|---|---|---|---|---|---|---|
0 | 1 | ||||||
Escribir color | Turno | Siguiente estado | Escribir color | Turno | Siguiente estado | ||
Estado actual | 0 | 1 | R | 0 | 1 | R | 1 |
1 | 0 | norte | 0 | 0 | norte | 1 |
La dirección a su vez, es uno de L (90 ° a la izquierda), R (90 ° a la derecha), N (sin giro) y U (180 ° giro en U ).
Ejemplos de
- Ejemplos de turmitas de dos colores de dos estados en una cuadrícula , todos a partir de una configuración vacía:
Crecimiento en espiral.
Producción de una carretera después de un período de crecimiento caótico.
Crecimiento caótico con textura distintiva.
Crecimiento con una textura distintiva dentro de un marco en expansión.
Construyendo una espiral de Fibonacci .
Construyendo un diamante en crecimiento
- Ejemplos de turmitas con más estados y colores y en cuadrículas no cuadradas:
Turmita de dos colores de tres estados que produce un patrón fractal similar a un copo de nieve .
Turmita tricolor de tres estados en una cuadrícula hexagonal , que crece caóticamente con una textura distintiva antes de atascarse en un bucle periódico después de aproximadamente 194150 pasos.
A partir de una cuadrícula vacía u otras configuraciones, los comportamientos más comúnmente observados son el crecimiento caótico, el crecimiento en espiral y la construcción de 'autopistas'. Los ejemplos raros se vuelven periódicos después de una cierta cantidad de pasos.
Juego de Busy Beaver
Allen H. Brady buscó turmitas terminales (el equivalente a castores ocupados ) y encontró una máquina de 2 colores y 2 estados que imprimía 37 1 antes de detenerse, y otra que daba 121 pasos antes de detenerse. [3] También consideró turmitas que se mueven en una cuadrícula triangular , encontrando varios castores ocupados aquí también.
Ed Pegg, Jr. consideró otro enfoque del ajetreado juego de los castores. Sugirió turmitas que pueden girar, por ejemplo, tanto a la izquierda como a la derecha, dividiéndose en dos. Los turmitas que luego se encuentran se aniquilan entre sí. En este sistema, un Busy Beaver es aquel que desde un patrón inicial de un solo turmitas dura más tiempo antes de que todos los turmitas se aniquilen entre sí. [6]
Otras rejillas
Siguiendo el trabajo inicial de Allen H. Brady de turmitas en una cuadrícula triangular, también se han explorado los mosaicos hexagonales . Gran parte de este trabajo se debe a Tim Hutton, y sus resultados se encuentran en el repositorio de tablas de reglas. También ha considerado a los turmitas en tres dimensiones y ha recopilado algunos resultados preliminares. Allen H. Brady y Tim Hutton también han investigado turmitas relativas unidimensionales en la red de enteros , que Brady denominó aletas . (Por supuesto, los turmitas absolutos unidimensionales se conocen simplemente como máquinas de Turing).
Ver también
- Autómata celular : un modelo discreto estudiado en informática
- Hormiga de Langton : máquina de Turing bidimensional con comportamiento emergente
- Gusanos de Paterson : una familia de autómatas celulares para modelar el comportamiento de alimentación
Referencias
- ^ Langton, Chris G. (1986). "Estudio de la vida artificial con autómatas celulares" (PDF) . Physica D: Fenómenos no lineales . 22 (1-3): 120-149. Código bibliográfico : 1986PhyD ... 22..120L . doi : 10.1016 / 0167-2789 (86) 90237-X . hdl : 2027,42 / 26022 .
- ^ Brady, Allen H. (1988). "El juego del castor ocupado y el significado de la vida". En Rolf Herken (ed.). La máquina universal de Turing: una encuesta de medio siglo . Springer-Verlag. ISBN 0-19-853741-7.
- ^ a b Brady, Allen H. (1995). "El juego del castor ocupado y el significado de la vida" . En Rolf Herken (ed.). La máquina universal de Turing: una encuesta de medio siglo (2ª ed.). Springer-Verlag. págs. 237-254. ISBN 3-211-82637-8.
- ^ a b Rucker, Rudy. "Laboratorio de vida artificial" . Consultado el 16 de octubre de 2009 .
- ^ Dewdney, AK (septiembre de 1989). "Recreaciones informáticas: máquinas de Turing bidimensionales y turmitas hacen pistas en un avión". Scientific American . 261 : 180-183. doi : 10.1038 / scientificamerican0989-180 .
- ^ Pegg, Jr., Ed. "Rompecabezas matemático" . Consultado el 15 de octubre de 2009 .
enlaces externos
- "Página web que muestra varios turmitas" . Archivado desde el original el 21 de diciembre de 2013.
- Pegg Jr., Ed (7 de junio de 2004). "Juegos de matemáticas: máquinas de Turing 2D" . MAA en línea. Archivado desde el original el 16 de mayo de 2013.
- Pegg Jr., Ed (27 de octubre de 2003). "Juegos de matemáticas: los gusanos de Paterson revisitados" . MAA en línea. Archivado desde el original el 23 de marzo de 2004.
- Turmite , en MathWorld .
- Guión de Golly para generar turmitas arbitrarias
- Turmitas de movimiento absoluto y relativo y castores ocupados en cuadrículas cuadradas, cúbicas, triangulares y hexagonales