Bloque 4 Maquinas de Turing

4.1 Definición formal de maquina de Turing

La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.

(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta , borrando el símbolo , escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

4.2 Construccion modular de una maquina de Turing

Mediante esta Técnica se pueden desarrollar maquinas de Turing complejas a partir de Bloques y apartir de maquinas mas pequeñas mediante diagramas de transiciones.

La construcción de maquinas de Turing se lleva a cavo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

Suponga que tenemos dos máquinas de Turing M1 y M2, con diagramas de tranciciones T1 y T2, respectivamente, y simbolos de cinta del conjunto . Si queremos desarrollar un diagrama de transiciones para otra máquina que simule las actividades de M1 seguidas por las de M2, bastaría con eliminar la designación de parada del estado de parada T1 y la caracteristica de inicio del estado inicial de T2, y luego dibujar un arco con etiqueta x/x para cada x en , del antiguo estado d eparada de T1 al antiguo estado inicial de T2.

(Este aprtado puede ser el deceado pero tiene desventajas)... Supongamos que queremos que la amquina compuesta se detenga después de simular M1, a menos que el símbolo actual, al llegar al estado de parada, sea z, en cuyo caso nos gustaria que la nueva máquina simulara las acciones de M2; o supongamos que necesitamos combinar 3 diagramas y controlar el paso de uno aotro dependiendo del valor del símbolo actual al llegar a cada uno de los antiguos estados de parada. En este caso re requiere un enlace mas complicado.

Si necesitamos combinar los diagramas de transiciones de varias máquinas que simule alguna combinación de las máquinas originales. Seguimos los siguientes pasos:

Elimine la característica de inicio de los estados iniciales de todas las máquinas, excepto la de aquél donde iniciará la máquina compuesta.

Elimine la caracyerística de detención de los estados de parada de todas las máquinas e introduzca un nuevo estado de parada que no se encuentre en ninguno de los diagramas que se combinan.

4.3 Lenguajes aceptados por la Maquina de Turing.

Una máquina de Turing se puede comportar como un aceptador de un lenguaje. Si colocamos una cadena w en la cinta, situamos la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena w y ponemos en marcha la  máquina a partir  de su estado inicial. Entonces w es aceptada si, después de una secuencia de movimientos, la máquina de Turing llega a un estado final y para. Por tanto w es aceptada. Si qw  *  w1pw2 para algún estado final p y unas cadenas w1 y w2.

 Entonces, se obtiene la siguiente definición: Sea M = (Q, S , G, q0=q1, B, F, d) una máquina de Turing. Entonces el lenguaje aceptado por M es: L(M) = {wÎ S*½q1w   *   w1pw2 para pÎF y wiÎG*}.

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.

Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos.

Gramáticas estructuradas por frases:

Parte   izquierda   de   las   reglas:   combinación   de   símbolos   terminales   y   no terminales, con al menos un no terminal.

Parte derecha de las reglas: combinación de símbolos terminales y no terminales de cualquier longitud (incluso 0).

Las máquinas de Turing aceptan lenguajes estructurados por frases.

Configuración de una máquina de Turing:

Contenido de la cinta: entre corchetes.

A la izquierda del símbolo actual se incluye el estado.

- Aceptación: secuencia de configuraciones de la máquina que  empieza  con  [iw]  y termina con [hY].

Teorema: Todo lenguaje estructurado por frases es aceptado por una máquina de Turing.

Demostración: Para cada gramática G existe una máquina de Turing no determinista M de 2 cintas que aceptas el lenguaje generado por G.

Construcción de la máquina:

1.   Se copia la cadena de entrada en la primera cinta.

2.   Se escribe S (símbolo inicial) en la cinta 2.

3.   Se aplican las reglas de reescritura de forma no determinista a la cadena de la cinta 2.

4.   Si la cinta 2 contiene sólo símbolos terminales, se compara con la cadena de la cinta 1. Si son iguales, el proceso ha terminado. Si no, provocar una terminación anormal.