Historia de La Máquina de Turing

               Historia de La Máquina de Turing 

La Máquina de Turing respondía a un intento de alcanzar una solución para uno de los problemas matemáticos más importantes a principios del siglo XX: el Entscheidungsproblem o Problema de Decisión. A pesar del nombre, cuando Alan Turing propuso su máquina en 1936, nunca pensó en una implementación física de la misma.Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.Inspirada en el modo de proceder de los calculistas humanos,  consistía en una cinta infinita con casillas que podían registrar ceros y unos, y una máquina de estados finitos (o cabezal) que podía avanzar o retroceder sobre la cinta y leer dígitos o escribirlos según el estado en que se encontrara. Inicialmente cada máquina computaba una única función, pero Turing se dio cuenta de que el programa para calcular una función u otra se podía codificar en la misma cinta que los datos de entrada, lo que dio lugar a la Máquina Universal de Turing, modelo teórico del computador digital. Dicha Máquina Universal podía emular cualquier máquina de Turing al recibir como entrada la codificación de una máquina particular al mismo tiempo que los datos. Al almacenar el programa en el mismo formato que los datos, quedaban delimitados los papeles que iban a desempeñar el hardware (de propósito general) y el software (tanto de sistema como de aplicaciones) en la informática actual.

Alan Turing introdujo el concepto de máquina de 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 que 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 sentencia matemá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.[6]​

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.[7]​

Mediante este modelo teórico y el análisis de la complejidad de los 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 pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.

Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo xx caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.[8]​

La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado solo una parte finita es accesible.