Maquina de turing

MÁQUINA DE TURING

Breve introducción a lo que es una máquina de turing







A continuación se tratará de hablar sobre lo que es la máquina de turing, se les presentara un breve abre bocas de quien inventa, como surge, como funciona y pequeños ejemplos de tan magnifico aporte a la humanidad como lo es la máquina de turing.


 
Máquina de Turing

Cuando se habla de algoritmosy computación es casi inevitable encontrar alguna referencia a la máquina de Turing.
En 1931, el matemático checo Kurt Godel descubrió que había teoremas matemáticos que eran verdaderos aun cuando no se pudiesen probar. Ante esto, Alan Turing se puso a investigar aquellos que sí podían ser probados. Quería intentar demostrar la vieja idea de que las matemáticas no son un arte misterioso, sinouna ciencia exacta regida por reglas lógicas.
Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera totalmente mecánica los procesos que normalmente llevaría a cabo un matemático. Había una máquina para cada proceso; así, había una máquina que sumaba, otra que multiplicaba, etc. Fue en ese entonces cuando estas máquinas acabarían por recibir el nombre de "Máquinas de Turing".
LaMáquina de Turing es un modelo computacional introducido por Alan en el trabajo "Sobre los números computables, con una aplicación a la Entscheidungsproblem (en castellano: problema de decisión)", publicado por la Sociedad Matemática de Londres, 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 puedaaplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.
Fue así que turing construyó el modelo formal de computador, la máquina de Turing, también 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.











Alan Turing y su “Maquina Turing”¿Cómo funciona?

Una máquina de Turing es un autómata más general, más completo a nivel de autómatas por decirlo así, 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 lasacciones 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 deoperaciones individuales muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.
Existen diversas "variedades" de una máquina de Turing, pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones:
 Tiene una cinta sobre la que puede desplazarse a izquierda y derecha uncabezal de lectura/escritura. La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito; este conjunto de símbolos se denomina el alfabeto de la máquina. En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #). La cinta puede contener tantas celdas a derecha eizquierda del cabezal como sean necesarias para el funcionamiento de la máquina.
 El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.
 Existe un registro de estado que almacena el estado de la máquina. El número de estados posibles es finito, y no se exige ningún estado...