- Máquina de Turing con Directiva de Permanecer
Recuérdese que la máquina de Turing sencilla sitúa la cabeza de lectura/escritura sobre el primer B que haya a la izquierda de la posición actual. Para hacerlo, busca fuera de la celda actual y retrocede. Esto es debido a la definición original que requiere que por cada transición se mueva la cabeza de la cinta.
La función de transición estaba definida como: d: Q x G ® Q x G x {R, L} y puede ser modificada como: d: Q x G ® Q x G x {R, L, S} donde S significa "permanecer", es decir no mover la cabeza de lectura/escritura.
Por tanto d (q, s)= (p, s ’, S) significa que se pasa del estado q al p, se escribe s’ en la celda actual y la cabeza se queda sobre la celda actual.
- Máquina de Turing Multipista
Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B). Por tanto, los movimientos que realice está máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.
Ejemplo: Para una máquina de Turing que sume dos números binarios. Primero se construye una máquina de Turing de tres pistas. La entrada serán dos números binarios que ocupen las dos pistas superiores de la cinta. Suponiendo que sus dígitos se alinean por la derecha, que sus representaciones binarias son de la misma longitud (lo que se puede conseguir rellenándolas con tantos ceros como sea necesario) y que la cabeza de lectura/escritura se sitúa sobre la celda del extremo izquierdo de la cadena. Por tanto, si tuvieran que sumar 101 y 10, la cinta debería contener
(B, B, B) (1, 1, B) (1, 1, 0) (1, 1, 1)
(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)
(0, 1, B) (0, 1, 0) (0, 1, 1)
(1, 0, B) (1, 0, 0) (1, 0, 1)
Esta máquina de Turing buscará primero hacia la derecha el extremo derecho de los números que van a ser sumados. Entonces sumará pares de dígitos, desde la derecha hacia la izquierda, llevando la cuenta de los resultados que se obtengan y sumando a quienes corresponda.
Por tanto, se obtiene (suponiendo que q1 es el estado inicial):
d (q1, s ) = (q1, s , R), si s ¹ (B, B, B) ó (q2, s , L), si s =(B, B, B)
d (q2, (0, 0, B)) = (q2, (0, 0, 0), L) d (q3, (0, 0, B)) = (q2, (0, 0, 1), L)
d (q2, (0, 1, B)) = (q2, (0, 1, 1), L) d (q3, (0, 1, B)) = (q3, (0, 1, 0), L)
d (q2, (1, 0, B)) = (q2, (1, 0, 1), L) d (q3, (1, 0, B)) = (q3, (1, 0, 0), L)
d (q2, (1, 1, B)) = (q3, (1, 1, 0), L) d (q3, (1, 1, B)) = (q3, (1, 1, 1), L)
d (q2, (B, B, B)) = (q4, (B, B, B), S) d (q3, (B, B, B)) = (q4, (B, B, B), S)
Obsérvese que se necesita que esta máquina de Turing tenga la posibilidad de no moverse.
- Máquina de Turing de Cinta infinita en una Dirección
Máquina de Turing que usa una cinta que se extiende infinitamente en una única dirección. Generalmente, se tiene una cinta que se extiende infinitamente hacia la derecha. No está permitido realizar ningún movimiento hacia la izquierda a partir de la celda del extremo izquierdo. Desde luego, cualquier máquina de Turing de esta forma puede ser simulada por una de las que responden a la definición original. Para cada computación, simplemente se marca una de las celdas de la cinta infinita por los dos lados, como la celda que se encuentra en el límite izquierdo.
- Máquina de Turing en Dos Direcciones
Una máquina de Turing con una cinta infinita en un sentido puede simular una máquina de Turing con la cinta infinita en los dos sentidos pero con dos pistas. Sea M una máquina de Turing con una cinta infinita en los dos sentidos. La máquina de Turing M’, que tiene una cinta infinita en un sentido, puede simular a M si tiene una cinta con dos pistas. La cinta superior contiene la información correspondiente a la parte derecha de la cinta M, a partir de un punto de referencia dado. La pista inferior contiene la parte izquierda de la cinta M (en orden inverso).
- Máquina de Turing Multicinta
La máquina de Turing multicinta tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento, esta máquina de Turing:
1. Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.
2. Escriben un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.
3. Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).
Por tanto, la función de transición para una máquina de Turing con n cintas, es de la forma d : Q x G n ® Q x G n x {R, L} n donde una transición de la forma d (q, (s 1, s 2,…, s n)) = (p,(t 1, t 2, …, t n), (X1, X2, …, Xn)) significa que cambia del estado q a p, reemplaza s i por t i en la cinta i y mueve la cabeza de la cinta i en la dirección Xi.
- Máquina de Turing Muldimensional.
La máquina de Turing multidimensional es aquella que permite que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, al derecha, hacia arriaba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing será de la forma:
d : Q x G ® Q x G x {R, L, U, D}
Una máquina de Turing multidimensional simula una máquina de Turing estándar. Simplemente realizando todas sus computaciones en una única dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por tanto, la complejidad y la flexibilidad adicional que se debe a la múltiple dimensión, no es una capacidad real. Para simular una máquina de Turing de dos dimensiones mediante una máquina de Turing estándar, primero se asociara una dirección a todas las celdas de la cinta. Una forma de hacerlo es fijar, de forma arbitraria, un lugar en la cinta a partir del cual se asignarán las coordenadas a las celdas de la misma forma que se realiza en un plano de coordenadas.
Entonces, se usara una cinta de dos pistas para simular la máquina de Turing. Una pista se encargará de almacenar el contenido de las celdas y la otra las coordenadas, utilizando un símbolo (*) para separar los valores de las coordenadas. Para simular un movimiento de una máquina de Turing de dos dimensiones, está máquina calcula la dirección de la celda a la que se moverá la máquina de Turing dos dimensiones. Entonces, localiza la pista inferior la celda con dicha dirección y cambia el contenido de la celda en la pista superior.
Máquina de Turing No determinista.
La máquina de Turing No determinista es aquella que para un estado actual y el símbolo actual de la cinta, puede haber un número finito de movimientos a elegir. Por lo tanto, la regla de transición d de dicha máquina, satisface
d (q, s ) Í Q x G x {R, L}
Por ejemplo, si la máquina de Turing tiene una transición
d (q1, a) = {(q1, b, R), (q2, a, L)} entonces los movimientos
abbq1ab abbbq1b y abbq1ab abq2bab son posibles.
Ya que cualquier máquina de Turing determinista es también no determinista, es lógico que una máquina de Turing determinista se pueda simular mediante una no determinista. También una máquina de Turing determinista puede simular una no determinista. Por tanto, no se gana ninguna potencia adicional a causa del no determinismo.
No hay comentarios:
Publicar un comentario