Máquina de Turing.
Enviado por Diana Vazquez O • 4 de Septiembre de 2016 • Resúmenes • 680 Palabras (3 Páginas) • 147 Visitas
Máquina de Turing
Alan Turing, Alonzo Church, entre otros personajes desarrollaron esquemas matemáticos para poder puntualizar qué era lo que si podía ser computado y que no. Lo llevaron a cabo durante la década de los 30’s.[pic 1]
Kurt Gödel expuso que existen problemas para los cuáles no hay solución lógica, a estos se les designa indecidibles. David Hilbert, un matemático, se preguntó si había un método para poder estipular cuáles problemas era indecidibles y cuáles no.
Para saber si un problema es decidible, deberá de ser resuelto mediante un procedimiento efectivo, esto es, un algoritmo.
En 1936, Turing expuso un formalismo lógico que representa el funcionamiento de algoritmos, una maquina abstracta. Turing señaló que todo lo que un humano puede computar, lo puede efectuar esta máquina.
Alan Turing introdujo el concepto de Máquina Turing en su trabajo On computable nubers, with an application to the Entsheidugpronlem, este fue publicado en 1936 por la Sociedad de Matemática de Londres.
La máquina de Turing es una caja negra, compleja como el ser humano y simple como una máquina de escritorio, capaz de no solo leer y escribir un alfabeto de símbolos finito a partir de una cantidad definida pero muy grande de cinta de papel, sino de modificar su propia configuración o “estado mental”.
Una máquina de Turing manipula símbolos de una cinta de entrada en función de unas reglas. Se define como un autómata, que mediante un cabezal lector que lee de una cinta de entrada símbolos de un alfabeto, cambiando entre estados en función de la entrada pudiendo rechazar o aceptar la cadena de entrada dependiendo del lenguaje que acepte. Dicha maquina era capaz de implementar cualquier problema matemático que pudiera representarse mediante un algoritmo. Formalmente se define en función de los estados que tiene dicho autómata el alfabeto de entrada y las transiciones que soportan. Es una herramienta básica para el campo de los autómatas y lenguajes formales.[pic 2]
La máquina de Turing está conformada por un cabezal lector/escritor y una cinta infinita en la que el cabezal puede leer el contenido, borrar el contenido anterior y escribir un nuevo valor. Las únicas operaciones que se pueden realizar en dicha maquina se limitan a: Avanzar el cabezal lector/escritor hacia la derecha.
Esta tabla toma como medidas el estado actual de la máquina y el carácter leído de la cinta, proporcionando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.
La memoria es la cinta de la máquina que se divide en espacios de trabajo designados como celdas, donde se pueden escribir y leer símbolos. Primeramente, todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que decretan el funcionamiento de la maquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolos, entonces este símbolo debe ser remplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha. [pic 4][pic 3]
...