Variantes de la maquina de turing

Variantes de la máquina de Turing
 
            Existen muchas alternativas de la máquina de Turing, incluyendo cintas múltiples o indeterminismo. Estas son llamadas variantes del modelo de la máquina de Turing. Tanto el modelo original como sus variantes tienen el mismo poder, es decir, reconocen la misma clase de lenguajes.
 
            Para ilustrar la robustez del modelo de la máquina deTuring, hagamos una variación de la función de transición permitida. En la definición original, la función de transición fuerza a la cabeza de la cinta a moverse a la izquierda o a la derecha después de cada paso, la cabeza de la cinta no puede permanecer sin movimiento. Supongamos que le damos a la máquina de Turing la habilidad para que la cabeza de la cinta permanezca sin movimiento. Lafunción de transición tendría la forma δ: Q x Γ → Q x Γ x { L, R, S }. ¿ Permitirá esta nueva característica aceptar reconocer lenguajes adicionales, dando más poder al modelo ? Por supuesto que no, ya que es posible convertir este nuevo tipo de MT en una MT original.
 
            Este pequeño ejemplo contiene la clave para mostrar la equivalencia de las variantes de la máquina de Turing. Para mostrarque dos modelos son equivalentes simplemente hay que mostrar que podemos simular un modelo en el otro.
 
4.2.1. Máquina de Turing multicinta
 
            Una máquina de Turing multicinta es como una máquina ordinaria con muchas cintas. Cada cinta tiene su propia cabeza de la cinta. Inicialmente la cadena de netrada se encuentra en la cinta 1 y las otras cintas están en blanco. La función detransción se modifica para permitir la lectura, escritura y movimiento de todas las cintas simultáneamente. Formalmente, se define como
                                                            δ: Q x Γk → Q x Γk x { L, R }k,
 
donde k es el número de cintas. La expresión
                                                                                    δ(qi, a1, …, ak) = (qj, b1, …, bk, L,R, …, L)
 
significa que, si la máquina se encuentra en el estado qi y las cabezas 1 a la k están leyendo los símbolos a1 hasta ak, la máquina va al estado qj, escribe los símbolos b1 hasta bk y mueve cada cabeza a la izquierda o derecha según se especifica.
 
            Pareciera que las máquinas de Turing multicinta son más poderosas que las máquinas de Turing ordinarias, pero podemosmostrar que son equivalentes. Recordemos que dos máquinas son equivalentes si reconocen el mismo lenguaje.
 
Teorema de equivalencia entre máquinas de Turing ordinarias y máquinas de Turing multicinta
 
            Cada máquina de Turing multicinta tiene una máquina de Turing ordinaria equivalente.
 
            DEMOSTRACIÓN
 
            Mostramos como convertir una MT multicinta M a una MT Scon una sóla cinta. La idea principal es mostrar como       simular M con S.
 
            Digamos que M tiene k cintas. Entonces S simula el efecto de k cintas almacenando la información de las cintas en         su cinta sencilla. S utiliza el símbolo # para delimitar el contenido de las cintas. Además del contenido de cada          cinta, S debe almacenar la posición de las cabezas. Esto sehace marcando el símbolo donde está colocada la             cabeza en cada cinta. En la figura 4.6 se ilustra como puede usarse una cinta para representar tres cintas.
 

 
Figura 4.6. Representando tres cintas con una sóla
 
            S = “Sobre la cadena de entrada w = w1 … wn
                        1. Primero S coloca su cinta en el formato que representa las k cintas de M. La cintacon el formato contiene
 
                                                    •                       •     •
                                                # w1 w2 … wn # Џ # Џ # … #
                        2. Para simular un movimiento, S barre su cinta desde el primero hasta el último símbolo # para determinar                                    los símbolos bajo las cabezas virtuales....