Máquina de turing

-------------------------------------------------
Máquina de Turing

Historia
Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application tothe 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, sihay 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.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante estemodelo 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 problemasdenominados P y NP, cuyas soluciones pueden encontrarse entiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.
Precisamente, la tesis de Church-Turing formuladapor Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XXcaracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.1
La idea subyacentees 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 unmomento determinado sólo una parte finita es accesible.

¿Qué es una maquina de turing?
La máquina de Turing es un modelo computacional introducido por Alan Turing en el trabajo “On computablenumbers, with an application to the Entscheidungsproblem”, 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...