Turmite

Archiu:Turmite-120121010011-8342.svg

Turmite

Archiu:Turmite-120121010011-8342.png

El turmite especificat com {{{1, 2, 0}, {1, 2, 1}}, {{0, 1, 0}, {0, 1, 1}}} es mostra en 8342 passos de temps.

En ciències de la computació, un Turmite és una màquina de Turing que es val d'una cinta bidimensional, fent alusió a la Teoria de la computabilidad, un Turmite té el mateix poder que una màquina de Turing determinista; pel fet que accepta i decidix el mateix tipo de llenguages (recursivamente enumerables i recursivos, respectivament) i computa exactament les mateixes funcions totals i parcials (les recursivas minimisades llimitades i les recursivas minimisades illimitades, respectivament), empero, en la teoria de la Complexitat computacional, un Turmite en $k$ caps resol un problema exactament en el mateix temps que ho resol una MT en $k$ cintes (sent $k$ el número mínim en el qual es conseguixca la màxima eficàcia), o siga, aproximadament en temps $O(\sqrt{n})$, sent $n$ el temps en el que eixe mateix problema és resolt per una MT determinista d'una sola cinta.

Definició formal

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

• $Q$ és un conjunt finito d'estats.
• $\Sigma \subseteq \Gamma$ és un conjunt finito de símbols d'entrada, l'alfabet d'entrada.
• $\Gamma$ és un conjunt finito de símbols de cinta, l'alfabet de cinta.
• $s\in Q$ és l'estat inicial.
• $b\in \Gamma$ és un símbol denominat blanc, i és l'únic símbol que es pot repetir un número infinit de voltes.
• $F\subseteq Q$ és el conjunt d'estats finals d'acceptació.
• $\delta :Q\times {\Gamma }^k\to Q\times {\Gamma }^k\times \{L,S,R{\}}^k$ és una funció parcial denominada funció de transició, a on L és un moviment a l'esquerra, S indica un no-moviment de cap i R és el moviment a la dreta; k és el número de caps dins de la cinta bidimensional.

Existixen moltes definicions vàlides per a un Turmite de la mateixa manera que moltes atres per a una MT, la diferència entre un Turmite i una MT no radica tant en la definició matemàtica utilisada per a establir una estipulació entre l'humà i la representació abstracta, sino que es reflectix pragmàticament, és dir, quàn parlem de moviments utilisarem la mateixa notació que s'utilisa per a les MT´s de cintes múltiples (Prenent cada cinta de la MT multicinta com un marcador en el Turmite), en açò en ment, una configuració d'un Turmite es denota:

$(q,(a$$b$$c{)}_1,\cdots ,(a$$b$$c{)}_k)$

a on $q$ és un estat del Turmite, $a$ i $c\in {\Gamma }^{*}$ i $b\in \Gamma$ és a on està posicionada una de les $k$ caps.

Un gra d'arena per a la Tesis de Church-Turing

La següent asseveració, "Una MT ordinària té el mateix poder (defugint l'eficàcia) que un Turmite (MT en cinta bidimensional)" és verdadera, i aporta un gra d'arena a una prova constructiva de que la Tesis de Church-Turing és verdadera també, com també es va demostrar que succeïx lo mateix en una MTN (MT no determinista), una Màquina de Post, un autómata finito en dos piles, un autómata finito en pila i 2 marcadors, una MT en sol 2 estats, el Joc de la vida de John Conway, un autómata celular, una gramàtica formal i uns atres models de computació descoberts (i encara per descobrir) no hipotètics, tots ells tenen el mateix poder que una MT i, en virtúd de la propietat transitiva de la relació "el mateix poder", el mateix poder que un Turmite lo que constituïxen una forma més o menys fidedigna de provar que esta Tesis és verdadera.

Vore també

• Problema de la parada (Un problema insoluble per a una MT, i per lo antedicho, insoluble per a un Turmite)