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:

• Cada ``('' ya empatado se marcará como ya revisado por una A y cada ``)'' se marcará por una B.
• Inicialmente, se busca el primer ``)'', yendo de izquierda a derecha.
• Por cada ``)'',
  • se marca con B,
  • se busca hacia la izquierda el primer ``('' que lo empate,
  • si no se encontrare tal ``('' la cadena está desequilibrada. En otro caso, el ``('' se marca con A y se repite este ciclo.
• Si quedaren ``('' no empatados, la cadena está desequilibrada. En otro caso se tiene equilibrio y se termina el proceso.

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.

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