Máquinas de turing

MÁQUINAS DE TURING
La máquina de Turing es un modelo computacional introducido por Alan Turing. 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, ydemostró 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.
Descripción
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 estamáquina se limitan a:
* avanzar el cabezal lector/escritor hacia la derecha.
* avanzar el cabezal lector/escritor hacia la izquierda.
El cómputo es determinado a partir de una tabla de estados de la forma:
* (estado, valor) (nuevo estado, nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para moverel cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
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 no determinismorespectivamente 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.
{P Y NP*: En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas(generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico. La clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no-determinista, la clase se llama NP.}
Laidea subyacente es el concepto de que una máquina de Turing es una máquina ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. La memoria se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen unsímbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”. La máquina de Turing puede considerarse como unautómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
Cómo funciona.
Existen diversas "variedades" de una máquina deTuring, 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 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...