Turmite

En ciencias de la computación, un Turmite es una Máquina de Turing que se vale de una cinta bidimensional, haciendo alusión a la Teoría de la computabilidad, un Turmite tiene el mismo poder que una Máquina de Turing determinista; por el hecho que acepta y decide el mismo tipo de lenguajes (enumerables recursivamente y recursivos, respectivamente) y computa exactamente las mismas funciones totales y parciales (las recursivas minimizadas limitadas y las recursivas minimizadas ilimitadas, respectivamente), empero, en la teoría de la Complejidad computacional, un Turmite con k cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con k cintas (siendo k el número mínimo con el cuál se logre la máxima eficacia), o sea, aproximadamente en tiempo $O(\sqrt n)$, siendo n el tiempo en el que ese mismo problema es resuelto por una MT determinista de una sola cinta.

Definición formal

Un Turmite es una 7-tupla $T=(Q, \Sigma, \Gamma, s, b, F, \delta)\,$, donde:

• $Q \,$ es un conjunto finito de estados.
• $\Sigma \subseteq \Gamma \,$ es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
• $\Gamma \,$ es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
• $s \in Q$ es el estado inicial.
• $b \in \Gamma$ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• $F \subseteq Q$ es el conjunto de estados finales de aceptación.
• $\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,S,R\}^k\,$ es una función parcial denominada función de transición, donde L es un movimiento a la izquierda, S indica un no-movimiento de cabeza y R es el movimiento a la derecha; k es el número de cabezas dentro de la cinta bidimensional.

Existen muchas definiciones válidas para un Turmite al igual que muchas otras para una MT, la diferencia entre un Turmite y una MT no radica tanto en la definición matemática utilizada para establecer una estipulación entre el humano y la representación abstracta, sino que se refleja pragmáticamente, es decir, cuándo hablamos de movimientos utilizaremos la misma notación que se utiliza para las MT´s de cintas múltiples (Tomando cada cinta de la MT multicinta como un marcador en el Turmite), con esto en mente, una configuración de un Turmite se denota:

(q,(ab$c)_1, \cdots ,(a$bc)_k)

donde q es un estado del Turmite, a y $c \in \Gamma^*$ y $b \in \Gamma$ es donde está posicionada una de las k cabezas.

Un grano de arena para la Tesis de Church-Turing

La siguiente aseveración, "Una MT ordinaria tiene el mismo poder (soslayando la eficacia) que un Turmite (MT con cinta bidimensional)" es verdadera, y aporta un grano de arena a una prueba constructiva de que la Tesis de Church-Turing es verdadera también, como también se demostró que sucede lo mismo con una MTN (MT no determinista), una Máquina de Post, un autómata finito con dos pilas, un autómata finito con pila y 2 marcadores, una MT con sólo 2 estados, el Juego de la vida de John Conway, un autómata celular, una gramática formal y otros modelos de computación descubiertos (y aún por descubrir) no hipotéticos, todos ellos tienen el mismo poder que una MT y, en virtúd de la propiedad transitiva de la relación "el mismo poder", el mismo poder que un Turmite lo que constituyen una forma más o menos fidedigna de probar que esta Tesis es verdadera.

Véase también

• Problema de la parada (Un problema insoluble para una MT, y por lo antedicho, insoluble para un Turmite)