Maquina De Turing Resumen

Maquina de Turing

Alan Mathison Turing fue un matemático, lógico, científico de la computación, criptógrafo, filosofo y maratonista y corredor de ultra distancia británico, y es considerado elpadre de la ciencia de la computación y de la informática moderna, también formalizo de los concepto del algoritmo y computación
Durante la Segunda Guerra Mundial, trabajó en descifrar los códigos nazis,particularmente los de la máquina Enigma y durante un tiempo fue el director de la sección Naval Enigma del Bletchley Park. Tras la guerra diseñó uno de los primeros computadores electrónicosprogramables digitales en el Laboratorio Nacional de Física del Reino Unido y poco tiempo después construyó otra de las primeras máquinas en la Universidad de Mánchester. La máquina de Turing es undispositivo de reconocimiento de lenguaje, es mas general que cualquier autómata finito y cualquier autómata de pila, debido que ellas pueden reconocer tanto el lenguaje regulare, como los lenguajesindependiente de contexto y demás muchos otros tipos de lenguajes.
La máquina de Turing tiene, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene lapalabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia a donde se extiende indefinidamente, llenándose los espacios con el carácter blanco. La cinta no infinita hacia la izquierda,por lo que hay un cuadro de la cinta que es extremo izquierdo, la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser bidireccionalmente. Por lo que puede pasar repetidasveces 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 finitosy 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...