M Quinas De Turing




Instituto Tecnológico Superior De Tepeaca

“Máquina de Turing ”
Asignatura:
Lenguajes y Autómatas 1
Asesor:
Ing. Daniel Neri Ramírez
Alumnos:
Camilo Romero Zayas
(12791013)
5”A” ISC
Periodo:
Agosto–Diciembre 2014

Máquinas de Turing
En 1937 en matemático ingles Alan Mathison Turing público un artículo famoso sobre los números calculables que desarrollo el teorema de Godiel y que puedeconsiderarse el origen oficial de informática teórica. En este artículo introdujo la máquina de Turing, y nos dice que es una entidad matemática abstracta que formalizo el concepto de algoritmo y resulto ser la precursora de las computadoras digitales. Con ayuda de su máquina Turing pudo demostrar que existen problemas irresolubles tales que ninguna máquina de Turing (y por ende ningún ordenador)será capaz de ordenar su solución, por lo que Alan Turing se le consideraba el padre de la teoría de la computabilidad.
Una maquina de Turing puede considerarse como una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo. Sobre dicha cinta actua un dispositivo que puede adoptar diversos estados y que en cada instante, lee un símbolo de la casilla sobre lo que estasituado. En función del símbolo que ha leído y del estado en que se encuentra, realiza las tres acciones siguientes: pasa a nuevo estado, imprime un símbolo en lugar del que acaba de leer, y se desplaza una posición hacia la izquierda, o hacia la derecha, o bien la maquina se para.
El funcionamiento de una maquina de Turing puede representarse mediante una tabla de doble entrada. Las filas estánencabezadas por los estados, las columnas por los símbolos escritos en la cinta. En cada poscicion de la tabla hay tres elementos: el estado siguiente, el símbolo que se escribe en la cinta y el movimiento de la cabeza.
La máquina de Turing (abreviado MT) tiene, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta esde longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el carácter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo, la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MTla cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta.
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 detransició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 detransición, para finalmente detenerse en un estado final o de aceptación, representando así la salida. 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 hacia la derecha. Avanzarel cabezal lector/escritor hacia 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)
COMO FUNCIONA
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...