Laboratorio
La máquina de Turing es un modelo computacional ideado por Alan Turing en el trabajo "On computable numbers, with an application to the Entscheidungs problem", publicado en 1936 para resolver cualquier operación matemática computable; es decir que se pueda realizar en forma mecánica. Su función es definir los cálculos a partir de las operaciones más sencillas posibles.
Las funciones que si pueden calcularse se llaman funciones computables o calculables.
La máquina de Turing universal es una máquina que puede ser capaz de simular el comportamiento de otro máquina Turing, gracias a la existencia de esta máquina ahora podemos disponer de ordenadores electrónicos que pueden realizar cualquier calculo computable.
La maquina de Turing es computacionalmente completa porque puede resolver cualquier problema recursivamente enumerable.
Ha encontrado su aplicaron en el campo de la complejidad de algoritmos en problemas que comparan las resoluciones de un problema, para detectar la dificultad de cada método.
El tipo de problemas NP-completos son imposibles de resolver en tiempo razonable cuando el numero de elementos es muy grande. Los campos de problemas P(sencillos) y NP(complejos), tienen relación con las maquinas Turing ya que sus nombres significan los que se pueden resolver en un tiempo polinómico(P) en una maquina de Turing determinista y los segundos los que se pueden resolver en una maquina de Turing no determinista(N)
Definición y funcionamiento
Las máquinas de Turing constan de una cinta dividida en casillas, hay un dispositivo que se encarga de desplazarse de casilla en casilla una a la vez, este dispositivo tiene un cabezal que lee el símbolo de la cinta, lo puede borrar e imprimir uno nuevo.
También tiene un registro que almacena los símbolos de los estados de las casillas, estos símbolos no tiene que ser iguales a los símbolos de lectura o escritura. En los ejemplos que voy a presentar más adelante los símbolos de lectura van a ser 0 y 1, aunque bien podrían ser cualquiera otros y los símbolos de estado los represento con letras también pueden ser cualquieras otros.
Su manera de funcionar es mecánica y secuencial, se obtiene el símbolo que hay en la casilla y el símbolo de estado, con estos dos datos se puede acceder a una tabla que va a indicar cuál va a ser el nuevo símbolo que se escribirá en la lista , el símbolo del estado y la dirección a desplazarse.
Aquí un ejemplo:
Lo que nos dice el primer renglón es que cuando se está en estado A y la casilla contiene un 0, este pasa a ser estado B y el 0 ahora es un 1, se desplaza hacia la derecha y ahora tenemos que cuando se está en estado A con un 1 en la casilla pasa a ser estado B y el uno se hace 0 y se desplaza a la izquierda.
El segundo renglón indica que cuando está en estado B y con un 0 en la casilla pasa a ser estado A y el 0 se hace 1 y se desplaza hacia la derecha, ahora cuando es estado B y contiene un 1 en la casilla pasa ser estado C y el 1 se hace 0 y el desplazamiento es hacia la derecha.
Y en el tercer renglón cuando tenemos estado C con un 0 en la casilla este pasa a ser estado A y el 0 se queda en 0 con un desplazamiento hacia la izquierda y cuando está en estado C con un 1 en la casilla se queda en estado C pero el 0 se 1 se convierte en 0.
La rutina borracintas
Se trata de escribir puros ceros en la cinta y que no quede niun uno, podría pensarse en hacer que se borren todos los unos que se encuentren y se remplacen por el 0
Pero esto solamente borraría un lado de la cinta el derecho a partir del punto de partida, entonces se tendría que modificar ese método:
Aunque este método aún tiene un problema, ¿Qué pasaría si hay más unos de un lado que del otro?, en este caso cuando la maquina termine de borrar todos los unos de un lado, se termina el proceso y quedarían los unos del otro lado sin ser borrado, entonces lo que se debe hacer para conseguir eliminar todos los unos es que cada vez que la maquina encuentre un uno le ponga un cero y escriba un uno en la posición siguiente y cambie su sentido, estos unos sirven como barreras así cada vez que la máquina encuentra un uno se desplaza una posición e invierte su sentido y así es como la máquina recorrerá por igual del lado derecho y el izquierdo.
Enlaces:
Luego vienen las máquinas Turing de múltiples cintas, la máquina universal, el problema de halting, el no-determinismo y todo lo que es bonito en la computación :) Cinco puntos para el lab.
ResponderEliminar