next up previous contents
Siguiente: Jerarquía de Chomsky en Un nivel arriba: Autómatas Anterior: Autómatas de pila no-deterministas

Máquinas de Turing

Estas son autómatas finitas con dos pilas que tienen un tope común. O equivalentemente, son autómatas que poseen una memoria dada por una cinta la cual es un almacenamiento lineal, infinito a ambos lados, con acceso a cualquier localidad en ella. El tope común es la casilla leída (``scanned cell''), una pila es la parte de la cinta a la derecha de la casilla leída y otra pila es su parte izquierda. Las transiciones de la máquina quedan determinadas por una función $t : Q \times T \rightarrow Q \times T \times \mbox{\it Mov\/}$, donde $\mbox{\it Mov\/} = \{\mbox{\it Der\/},\mbox{\it Izq\/}\}$. Esta vez, la relación $t(q,a) = ( p, b, \mu )$ se interpreta como sigue: ``Si se está en el estado q y se lee el símbolo a entonces se escribe b, se pasa a p y se va a examinar la casilla al lado $\mu$ de la leída''. De hecho, la relación $t(q,a) = ( p, b, \mu )$ puede escribirse como $(q,a;p,b,\mu)$, y por esto, decimos que una máquina de Turing queda especificada por su lista de quíntuplas. O, abusando aún más del lenguaje, que una lista de quíntuplas es el programa correspondiente a una máquina de Turing.


Ejemplo: Cadenas equilibradas de paréntesis Para tener una cadena equilibrada, cada ``)'' en ella ha de ``empatar'' con un correspondiente ``('' que lo anteceda. Para reconocer cadenas equilibradas procederemos como sigue: El procedimiento queda descrito por la lista de quíntuplas mostrada en la tabla (5).
 
Table 5: Máquina de Turing para reconocer cadenas equilibradas de paréntesis.
$1,x;1,x,\mbox{\it Der\/}$ : con cualquier cosa, salvo ``)'', aváncese a la derecha, $x\in\{(,b,A,B\}$,
$1,);2,B,\mbox{\it Izq\/}$ : con el primer ``)'', márquese y retrocédase,
$1,b;3,b,\mbox{\it Izq\/}$ : si la lista se acaba, revísese que todo haya sido marcado,
$2,y;2,y,\mbox{\it Izq\/}$ : con cualquier cosa, salvo ``('', continúese el retroceso, $y\in\{),b,A,B\}$,
$2,(;1,A,\mbox{\it Der\/}$ : márquese el ``('' que empata y repítase el ciclo,
$2,b;4,\mbox{\it No\/},\mbox{\it Alt\/}$ : se termina la cadena y no existe el correspondiente ``(''. No hay equilibrio.
$3,x;3,x,\mbox{\it Izq\/}$ : retrocédase ignorando las marcas, $x\in\{A,B\}$,
$3,(;3,\mbox{\it No\/},\mbox{\it Alt\/}$ : si quedare un ``('', éste ya no podría empatarse. No hay equilibrio.
$3,b;3,\mbox{\it S\'\i\/},\mbox{\it Alt\/}$ : se agotó la cadena y todo se marcó. Sí hay equilibrio.

Los cuatro estados de la máquina tienen una interpretación evidente:

\begin{eqnarray*}1 &:& \mbox{\rm avanza a la derecha buscando \lq\lq )'',} \\
2 &:&...
...odo haya sido marcado,} \\
4 &:& \mbox{\rm estado terminal.}
\end{eqnarray*}


Como mero ejemplo, en la tabla (6) mostramos la computación correspondiente a una cadena dada. En cada instante, la casilla leída es la adyacente a la derecha del estado actual, el cual se escribe en negritas.
  
Table 6: Un ejemplo del funcionamiento de la máquina de Turing que reconoce cadenas equilibradas de paréntesis.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert c\vert\vert c\vert\vert...
...\
\end{array}
\\ \hline \hline
\end{array}\end{displaymath}
\end{table}


next up previous contents
Siguiente: Jerarquía de Chomsky en Un nivel arriba: Autómatas Anterior: Autómatas de pila no-deterministas
Guillermo Morales-Luna
2000-06-27