Alan Turing aportaciones a la Ciencia y a la informatica

En el año de 1937, Turing, publicó un célebre artículo en el que definió una máquina calculadora de capacidad infinita, este es un dispositivo de reconocimiento de lenguaje, la máquina de Turingtiene un control infinito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta no es infinita hacia la izquierda, por lo que hay uncuadro de la cinta que es el extremo izquierdo, la MT la cabeza lectura y escritura, además de que en la MT la cabeza se mueve bidireccionalmente, por lo que puede pasar repetidas veces sobre unmismo 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 unconjunto 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 pertenecientes al alfabeto de entrada. Luego valeyendo 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 de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida. La máquina de Turing consta de un cabezallector/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 elcabezal lector/escritor hacia la derecha. Avanzar el 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). En pocas palabras la máquina de Turing describió en términos matemáticos precisos cómo un sistema automático con reglas extremadamente simples podía efectuar toda clase de...