La Maquina De Turing

¿Qué es una maquina de turing?

La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo. Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla , donde Q es un conjunto finito de estados Γ es un conjunto finito de símbolos de cinta, el alfabeto de cinta

 es el estado inicial 
 es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces 
 es el conjunto de estados finales de aceptación 
 es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha. 

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo como símbolo de “no movimiento” en un paso de cómputo.

¿Como funciona una maquina de turing?

Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario.

Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.

Una instrucción típica podría ser: 0111011i

La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso (la cinta se moverá hacia la derecha).

A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla:

Empezamos a leer por la izquierda el bianrio expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría. El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101 que es el número original.

Descripción La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

Avanzar el cabezal lector/escritor para la derecha; • avanzar el cabezal lector/escritor para la izquierda. El cómputo es determinado a partir de una tabla de estados de la forma: (Estado, valor)-→(\nuevo estado, \nuevo valor, dirección)

Definición Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla M=(Q,L,s,b,F,o) , donde •Q es un conjunto finito de estados. •L es un conjunto finito de símbolos de cinta, el alfabeto de cinta. •s E Q es el estado inicial. •b E L es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces. •F _C Q es el conjunto de estados finales de aceptación. •o : Q x L → Q x L x {L,R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S como símbolo de “no movimiento” en un paso de cómputo o el símbolo Σ para indicar el alfabeto de entrada.

Ejemplo Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo “1″ de una serie. La máquina de Turing copiará el número de símbolos “1″ que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada “111″ devolverá “1110111″, con “1111″ devolverá “111101111″, y sucesivamente.

El conjunto de estados es {s1,s2,s3,s4,s5} y el estado inicial es s1. La tabla que describe la función de transición es la siguiente:

El funcionamiento de una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

La máquina realiza su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa a ser s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su cómputo.

Máquina de Turing Cuántica En 1985, Deutsch presentó el diseño de la primera Máquina Cuántica basada en una máquina de Turing. Con este fin enunció una nueva variante la tesis de Church dando lugar al denominado “Principio de Church-Turing-Deutsch”. La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clásica. Está compuesta por los tres elementos clásicos: •Una cinta de memoria infinita en que cada elemento es un Qu Bit? •Un procesador finito •Un cursor

Diagrama de transición para la maquina de turing

Las transiciones de una maquina de turing pueden representarse visualmente, un diagrama de transición esta formado por un conjunto de nodos que nodos que corresponde a los estados de la MT. En un arco que vaya del estado q al esta p, apareceran una o varias etiquetas de la forma X/YS, donde X e Y son símbolos de cintan y S indica un sentido, que puede se I o D. es decir, si δ(q,X) = (p,Y,S),en el arco que va de q a p se encontrara la etiqueta X/YS.

QUIROZ MONTES KAREN PATRICIA