Matematicas Discretas

Luis Orozco 1150561 -Henry Pérez 1150556 Matemáticas Discretas

MAQUINA DE TURING

R
eseña biográfica de Alan Turing Alan Mathison Turing, OBE (23 de junio de 1912 en Maida Vale, Londres - 7 de junio de1954 en Wilmslow, Cheshire) fue un matemático, informático teórico, criptógrafo y filósofoinglés. Es considerado uno de los padres de la Ciencia de la computación siendo el precursor de lainformática moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión de la hoy ampliamente aceptada Tesis de Church-Turing, la cual postula que cualquier modelo computacional existente tiene las mismas capacidades algorítmicas, o un subconjunto, de las que tiene una máquina de Turing. Diseñó uno de los primeroscomputadores electrónicos programables 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. Entre otras muchas cosas, también contribuyó de forma particular e incluso provocativa al enigma de si las máquinas pueden pensar, es decir a la Inteligencia Artificial. En 1954, se suicidó

L

amáquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres en 1936, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentenciamatemática y que nos diga si esa sentencia es cierta o no. Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo. La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee elcontenido, 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. • avanzar el cabezal lector/escritor hacia la izquierda. El cómputo es determinado a partir de una tabla de estados de la forma:

Luis Orozco 1150561 -Henry Pérez 1150556 Matemáticas Discretas
(estado, valor)[pic](nuevo estado, nuevo valor, dirección) DEFINICIÓN FORMAL Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla [pic], donde • [pic]es un conjunto finito de estados. • [pic]es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina. • [pic]es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. • [pic]es el estadoinicial. • [pic]es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces. • [pic]es el conjunto de estados finales de aceptación. • [pic]es una función parcial denominada función de transición, donde [pic]es un movimiento a la izquierda y [pic]es el movimiento a la derecha.

E

xisten en la literatura un abundante número de definicionesalternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo [pic]como símbolo de "no movimiento" en un paso de cómputo o el símbolo [pic]para indicar el alfabeto de entrada. Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a serescrito en la cinta. Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar. Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo...