Ver el código de «Turmite»

[[Archivo:Turmite-120121010011-8342.png|miniaturadeimagen|El turmite especificado como {<nowiki>{{1, 2, 0}, {1, 2, 1}}</nowiki>, <nowiki>{{0, 1, 0}, {0, 1, 1}}</nowiki>} se muestra en 8342 pasos de tiempo.]]
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 ([[Lenguaje recursivamente enumerable|recursivamente enumerables]] y [[Lenguaje recursivo|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 <math>k</math> cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con <math>k</math> cintas (siendo <math>k</math> el número mínimo con el cual se logre la máxima eficacia), o sea, aproximadamente en tiempo <math>O(\sqrt n)</math>, siendo <math>n</math> 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]] <math>T=(Q, \Sigma, \Gamma, s, b, F, \delta)\,</math>, donde:

* <math>Q \,</math> es un [[conjunto finito]] de [[Estado físico|estados]].
* <math>\Sigma \subseteq \Gamma \,</math> es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
* <math>\Gamma \,</math> es un conjunto finito de símbolos de cinta, el alfabeto de cinta. 
* <math>s \in Q</math> es el estado inicial.
* <math>b \in \Gamma</math> es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
* <math>F \subseteq Q</math> es el conjunto de estados finales de aceptación.
* <math>\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,S,R\}^k\,</math> 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:

<math>(q,(a</math><math>b</math><small><math>c)_1, \cdots ,(a</math></small><math>b</math><math>c)_k)</math>

donde <math>q</math> es un estado del Turmite, <math>a</math> y <math>c \in \Gamma^*</math> y <math>b \in \Gamma</math> es donde está posicionada una de las <math>k</math> 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 solo 2 estados, el [[Juego de la vida]] de [[John Horton Conway|John Conway]], un [[autómata celular]], una [[gramática formal]] y otros [[Modelo de computación|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)

{{Control de autoridades}}
[[Categoría:Máquinas de Turing]]