Motor

MAQUINAS DE TURING
DEFINICIONES BASICAS.
La maquina de turing no es un objeto físico, sino un artificio matemático que nos proporciona un modelo de computación en el cual encuadramos el análisis de nuestros algoritmos.
La máquina de Turing fue introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por laSociedad 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 sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing construyó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina nopodí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 el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
 avanzar el cabezallector/escritor hacia la derecha.  avanzar el cabezal lector/escritor hacia la izquierda.
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 polinómico son encontradas según el determinismo y nodeterminismo respectivamente de la máquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.

Una máquina de Turing con una sola cinta puede ser definida comouna 7-tupla

MAQUINAS 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 escribirnuevos 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 muysencillas 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 un cabezal delectura/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 e izquierda del cabezal comosean 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...