Siguiente: Computabilidad-Turing Un nivel arriba: Máquinas de Turing Anterior: Computaciones en máquinas de

Modelos restringidos de máquinas de Turing

Presentaremos algunas variantes de las máquinas de Turing y veremos que son equivalentes. Mostraremos las equivalencias entre las diversas modificaciones de las máquinas de Turing de manera más bien coloquial. Anque se puede presentar demostraciones rigurosas en base a descripciones instantáneas, aquí las omitiremos con la certeza de que el lector podrá construirlas a partir de las indicaciones que presentamos. ${\cal MT}$ denotará a la clase de máquinas de Turing tal como las hemos definido. Diremos que dos clases de máquinas ${\cal M}_1$ y ${\cal M}_2$ son equivalentes si toda máquina en una clase es simulada por una máquina en la otra, es decir,

• $\forall M_1\in{\cal M}_1\exists M_2\in{\cal M}_2\forall \mbox{\bf x}: c(M_1(\mbox{\bf x}))=M_2(c(\mbox{\bf x})),$ y
• $\forall M_2\in{\cal M}_2\exists M_1\in{\cal M}_1\forall \mbox{\bf y}: d(M_2(\mbox{\bf x}))=M_1(d(\mbox{\bf x})),$

donde c y d son funciones apropiadas de conversión de palabras de un alfabeto a otro, considerando los alfabetos de ambas máquinas, que cumplen además $c(\uparrow)=\uparrow=d(\uparrow)$. Máquinas con cintas semi-infinitas, ${\cal MTSI}$: Estas son máquinas de Turing donde las casillas de la cinta se ponen en correspondencia con $I\!\!N$ mas no con $Z\!\!\!Z$, es decir, la cinta de cada máquina de esta clase tiene una casilla inicial a la izquierda, digamos c₀, y se prolonga indefinidamente a la derecha.

Proposición 6.1   ${\cal MT}$ y ${\cal MTSI}$ son equivalentes.

En efecto, por un lado, tenemos que toda máquina ${\cal MTSI}$ es en sí del tipo ${\cal MT}$. Recíprocamente, enumeremos las casillas de la cinta semi-infinita C como $c_0,c_1,\ldots,c_n,\ldots$ Dada una máquina M del tipo ${\cal MT}$ enumeremos a las casillas de la cinta de M como $\ldots,d_{-n},\ldots,d_{-1},d_0,d_1,\ldots,d_n,\ldots$ Pongamos un símbolo especial S en c₀ e identifiquemos al sector ``negativo'' de la cinta de M con las casillas impares de C y al ``no-negativo'' de M con las casillas pares de C:

$$\forall n> 0:(d_{-n}\leftrightarrow c_{2n-1})\land(d_{n-1}\leftrightarrow c_{2n+2})$$

Observamos que el movimiento hacia una casilla contigua en la cinta de M se traduce a dos movimientos contiguos en C. Cada vez que se ``atraviesa'' S en C se cambia de sentido: Un movimiento a la derecha en M corresponde a dos hacia la izquierda en C y viceversa. Hechas estas observaciones, de manera directa se puede simular a M usando C. Máquinas con cintas de varias pistas, ${\cal MTVP}$: Estas son máquinas de Turing cuyas cintas tienen varias ``pistas''. Pueden verse también como máquinas de varias cintas con movimientos ``sincronizados'': Movimiento que se hace en una cinta, se hace en todas.

Proposición 6.2   ${\cal MT}$ y ${\cal MTVP}$ son equivalentes.

En efecto, por un lado, tenemos que toda máquina ${\cal MT}$ es en sí del tipo ${\cal MTVP}$. Recíprocamente, dada una máquina M^k del tipo ${\cal MTVP}$ con k pistas, la podemos simular con una máquina M del tipo ${\cal MT}$ de cualquiera de las dos maneras alternativas:

1.

Si A es el alfabeto de M^k, entonces en cada momento el funcionamiento de M^k depende de la lista de k símbolos que aparece en la casilla actual, consistente de k casillas, una por cada pista. Esto define a una máquina del del tipo ${\cal MT}$ sobre el alfabeto A^k que es una potencia cartesiana del original.

2.

Consideremos una cinta de una sola pista en donde sus casillas se agrupan en bloques de k casillas. La posición j-ésima de la i-ésima pista en la cinta de M^k corresponde a la posición $((j-1)\cdot k+i)$-ésima de la nueva cinta. En esta nueva, casillas contiguas en lamisma pista de M^k distanciarán de k casillas. El mecanismo de funcionamiento se modifica para que cada movimiento de M^k obligue a revisar un bloque de k casillas y haga la modificación correspondiente, trabajando siempre en bloques.

Máquinas con cintas de varias cintas, ${\cal MTVC}$: Estas son máquinas de Turing con varias cintas con movimientos ``independientes''.

Proposición 6.3   ${\cal MT}$ y ${\cal MTVP}$ son equivalentes.

Demostraremos que ${\cal MTVP}$ y ${\cal MTVC}$ son equivalentes. En efecto, por un lado, tenemos que toda máquina ${\cal MTVP}$ es en sí del tipo ${\cal MTVC}$. Recíprocamente, dada una máquina $M^{\mbox{\scriptsize\it ind}}$ del tipo ${\cal MTVC}$ con k pistas, la podemos simular con una máquina $M^{\mbox{\scriptsize\it sinc}}$ del tipo ${\cal MTVP}$, con 2k pistas como sigue: Cada cinta C_j da origen a dos pistas P_j0,P_j1. La pista P_j1 tiene el mismo contenido que la cinta C_j. La pista P_j0 está en blanco salvo en la posición donde se encuentra la j-ésima cabeza lectora de $M^{\mbox{\scriptsize\it ind}}$, en la cual hay una marca `` $\downarrow$'' para marcar que ésa es la casilla escudriñada en la j-ésima cinta. Con esto, la máquina $M^{\mbox{\scriptsize\it sinc}}$ se construye de manera inmediata. Máquinas con dos símbolos, ${\cal MT}01$: Estas son máquinas de Turing sobre el alfabeto (0+1).

Proposición 6.4   ${\cal MT}$ y ${\cal MT}01$ son equivalentes.

En efecto, por un lado, tenemos que toda máquina ${\cal MT}01$ es en sí del tipo ${\cal MT}$. Recíprocamente, dada una máquina M del tipo ${\cal MT}$ sobre un alfabeto con m símbolos, sea $k=\lceil\log_2 m\rceil$. Cada símbolo en el alfabeto puede codificarse mediante una cadena de k bits. Por tanto M puede verse como una m''aquina de k pistas. De acuerdo con la segunda construcción de la máquina del tipo ${\cal MT}$ simuladora de una máquina del tipo ${\cal MTVP}$, obtenemos una máquina del tipo ${\cal MT}01$ que simula a M.
Siguiente: Computabilidad-Turing Un nivel arriba: Máquinas de Turing Anterior: Computaciones en máquinas de