Siguiente: Modelos restringidos de máquinas Un nivel arriba: Máquinas de Turing Anterior: Ejemplo: Cadenas equilibradas de

  
Computaciones en máquinas de Turing

Veamos aquí un enfoque formal a las máquinas de Turing. Una máquina de Turing es una estructura de la forma M=(Q,A,t,q₀,F) donde,

$$\begin{eqnarray*}Q &:& \mbox{\rm es un conjunto de {\em estados},} \\ A &:& \m... ...\\ F &:& \mbox{\rm es el conjunto de {\em estados finales}.} \end{eqnarray*}$$

De manera convencional se dice que

• M es determinista si t es una función $t:Q\times A\rightarrow Q\times A\times \mbox{\it Movs}$,
• M es indeterminista si t es una mera relación,

Una descripción instantánea (DI) es una cadena de la forma

$$\mbox{\bf y}qa\mbox{\bf x} \equiv\ldots y_{-3}y_{-2}y_{-1}qa ... ...}x_{3}\ldots \in A^{-I\!\!N}\times Q\times A\times A^{+I\!\!N},$$

con y_-i=a₀=x_j c.t.p.-(i,j) (casi en todas partes resepcto a i,j). q es el estado de la DI. Su interpretación es, naturalmente, la siguiente:

``El contenido de la cinta es $\mbox{\bf y}a\mbox{\bf x}$, se está examinando el carácter a y el control finito de la máquina está en el estado q.''

Alternativamente podemos distinguir a un símbolo de marca ``$\bullet$'' para reconocer inicios y terminaciones de DI's. Una DI es inicial o final según lo sea su estado. Si $\mbox{\bf y}q_0a\mbox{\bf x}$ es inicial decimos que la descripción inicial corresponde a la entrada $a\mbox{\bf x}$. Si $\mbox{\bf y}q_Fa\mbox{\bf x}$ es final decimos que la máquina deja a la salida $\mbox{\bf y}$. Escribimos $\mbox{\bf y}qa\mbox{\bf x}\rightarrow\mbox{\bf y}'q'a'\mbox{\bf x}'$ si es que existe una transición $(q,a,q',b,m)\in t$ tal que

$$\left\{\begin{array}{ll} \left\{\begin{array}{rcl} \mbox{\b... ...right. &\mbox{\rm si $m=\mbox{\rm Izq}$. } \end{array}\right.$$

`` $\stackrel{*}{\rightarrow}$'' es la cerradura reflexivo-transitiva de la relación `` $\rightarrow$''. Si $q_0\mbox{\bf x}$ es inicial, $\mbox{\bf y}q_F$ es final y $q_0\mbox{\bf x}\stackrel{*}{\rightarrow}\mbox{\bf y}q_F$ entonces decimos que M converge para la entrada $\mbox{\bf x}$ y, escribimos $M(\mbox{\bf x})=\mbox{\bf y}$. Si $\mbox{\bf DI}=\left\{\mbox{\it DI}_i\right\}_{i=0,\ldots,k}$ es una sucesión de DI's tal que $\mbox{\it DI}_0=q_0\mbox{\bf x}$, $\mbox{\it DI}_k=\mbox{\bf y}q_F$ y $\forall i<k:\left(\mbox{\it DI}_i\rightarrow\mbox{\it DI}_{i+1}\right)$ entonces decimos que $\mbox{\bf DI}$ es una computación terminal que transforma la DI inicial en la final. Si $\mbox{\it DI}_k$ no corresponde a un estado final, la computación se dice ser intermedia. Así pues, si M es una máquina y $\mbox{\bf x}$ es el contenido inicial en su cinta, $M(\mbox{\bf x})$ denotará al contenido que queda en la cinta cuando M se para a partir de $\mbox{\bf x}$. Indicaremos que M no se para a partir de $\mbox{\bf x}$ escribiendo $M(\mbox{\bf x})=\uparrow$, en el cual caso, diremos que M diverge con $\mbox{\bf x}$.
Siguiente: Modelos restringidos de máquinas Un nivel arriba: Máquinas de Turing Anterior: Ejemplo: Cadenas equilibradas de