Turmite

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

• ${\displaystyle Q\,}$ es un conjunto finito de estados.
• ${\displaystyle \Sigma \subseteq \Gamma \,}$ es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
• ${\displaystyle \Gamma \,}$ es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
• ${\displaystyle s\in Q}$ es el estado inicial.
• ${\displaystyle 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.
• ${\displaystyle F\subseteq Q}$ es el conjunto de estados finales de aceptación.
• ${\displaystyle \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:

${\displaystyle (q,(a}$${\displaystyle b}$${\displaystyle c)_{1},\cdots ,(a}$${\displaystyle b}$${\displaystyle c)_{k})}$

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

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 solo 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.

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