Máquina de Turing

TECNOLOGIA UNIVERSIDAD

INTRODUCCIÓN

Alan Mathison Turing, OBE (Paddington, Londres, 23 de junio de 1912 - Wilmslow, Cheshire, 7 de junio de 1954), fue un matemático, lógico, científico de la computación, criptógrafo y filósofo británico.

Es considerado uno de los padres de la ciencia de la computación siendo el precursor de la informá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.

 

 


Fuente: Wikipedia Alan_Turing

En el artículo On Computable Numbers, Turing construyó un modelo formal de computador, la Máquina de Turing, (con esto resolvió el entscheidungsproblem (planteado por, David Hilbert) y demostró que había problemas tales que una máquina no podía resolver. La máquina de Turing es el primer modelo teórico de lo que luego sería un computador programable. Con el tiempo a este tipo de máquina se la conoció como máquina de estado finito, debido a que en cada etapa de un cálculo, la siguiente acción de la máquina se contrastaba con una lista finita de instrucciones de estado posibles.

Para dar una definición matemáticamente precisa de lo que es un algoritmo, Turing ideó un dispositivo imaginario al que denominó Máquina de computación lógica LCM ("Logical Computing Machine"), pero que ha recibido en su honor el nombre de Máquina de Turing.

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

En realidad la máquina de Turing es más una abstracción matemática que un dispositivo físico o mecánico. El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.

Una máquina de Turing es un autómata que consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda. Por supuesto también consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba.

Tiene una propiedad sorprendente, y es que es capaz de implementar cualquier problema matemático que se nos ocurra, con la única condición de que éste se pueda expresar por medio de un algoritmo (que recordemos que no es más que estructurar el problema en un número de pasos determinados) Por tanto, podremos escribir una cadena de símbolos que represente el problema de manera que la máquina lo pueda leer y, como además también puede escribir y borrar, cuando vayamos de un paso a otro del algoritmo podrá recordar el paso en el que se encuentra en cada momento para así poder dar el siguiente en la dirección correcta.

(Puede quitar la publicidad ampliando la cuenta)