Maquinas Turing(Puntos extras)

¿QUE SON Y COMO FUNCIONAN?
Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador, existe un cambio en la representación del estado, usando para ello los números del 0 al 99, para permitir un mayor número de ellos.
La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.
Para entender mejor el funcionamiento de dicha maquina, vamos a ver un simple ejemplo: sea la máquina de Turing capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de Turing, el número de símbolos a usar podía ser cualquiera, con la única condición de ser un número finito, y no tenían por qué ser números; sin embargo, en aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los estados A, B y C (una máquina de Turing puede tener cualquier número de estados; la única condición es que sea un número finito). Supongamos que definimos la siguiente tabla:
estado símbolo nuevo nuevo sentido de
inicial leído estado símbolo avance

A 0 B 1 DERECHA
A 1 B 0 IZQUIERDA
B 0 A 1 DERECHA
B 1 C 0 DERECHA
C 0 A 0 IZQUIERDA
C 1 C 0 DERECHA
La cual vamos a simplificar de la siguiente manera:
0 1

A B,1,> B,0,< B A,1,> C,0,>

C A,0,< C,0,>
Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresado el nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta:
cabezal
v
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los sucesivos pasos de esta máquina si partimos del estado A:
1) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 1 0 0 0 0 ... escribir un 1 y movernos a la derecha

2) B El estado es B y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 1 0 1 0 0 0 0 ... escribir un 1 y movernos a la derecha

3) A El estado es A y leemos un uno;
v luego debemos cambiar al estado B,
... 0 0 0 1 1 1 0 0 0 0 ... escribir un 0 y movernos a la izquierda

4) B El estado es B y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 1 0 0 0 0 0 ... escribir un 0 y movernos a la izquierda

5) C El estado es C y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 0 0 0 0 0 0 ... escribir un 0 y movernos a la derecha

6) C El estado es C y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 0 y movernos a la izquierda

7) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 1 y movernos a la derecha
La ejecución de esta máquina seguiría indefinidamente, rellenando la cinta con unos y ceros de una manera más o menos aleatoria. Realmente, una máquina de Turing útil debería poder detenerse; esto es, tener un estado en el que se detiene. Dicho estado se alcanzaría igual que cualquier otro estado. Esto es, supongamos que el estado D es el de paro; lo único que debemos hacer es que, cuando la máquina halla terminado el cálculo, pase a estado D; de este modo se detiene y permite examinar la cinta para buscar el resultado.
Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de Turing puede hacer cosas útiles, tales como sumar dos números, multiplicarlos, copiarlos, etc. Disponiendo de una máquina con el suficiente número de estados, podríamos hacer con ella cualquier operación que un ordenador normal pudiese realizar.
Las máquinas de Turing plantean una deducción bastante curiosa: dado que en ellas se puede realizar cualquier trabajo computable, es posible programarlas para que simulen el comportamiento de un potente ordenador. Y como una máquina de Turing puede ser codificada en CUALQUIER ordenador, por pequeño que sea, sería posible (si disponemos de memoria suficiente, claro) emular en nuestro ordenador de casa una máquina de Turing que simule un superordenador. Esto significa que todos los ordenadores pueden realizar exactamente el mismo tipo de tareas, y que los cálculos que pueda realizar el más grande los puede llevar a cabo también el más pequeño. La única diferencia sería, obviamente, la velocidad.
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.
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.