Máquina de turing

Máquina de Turing

De Wikipedia, la enciclopedia libre

Saltar a navegación, búsqueda
La máquina de Turing es un modelo computacional introducido por Alan 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 cual se estudiaba la cuestión planteada por David Hilbert sobre si lasmatemá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 no podía resolver. La máquina de Turing es un modelo matemático abstracto que formaliza el concepto de algoritmo.
[pic][pic]
Diagrama artístico de una máquina de Turing.

|Contenido |
|[ocultar] |
|1 Descripción |
|2 Definición|
|3 Ejemplo |
|4 Máquinas de Turing deterministas y no deterministas |
|5 Máquina Universal de Turing |
|6 Máquina de Turing Cuántica|
|7 Véase también |
|8 Enlaces externos |


[pic][editar] 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. Lasoperaciones que se pueden realizar en esta má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) [pic](nuevo estado, nuevo valor, dirección)
Esta tabla toma como parámetros el estado actual de la máquina y el carácterleído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales deacuerdo 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 determinismo 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 deChurch-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.
La idea subyacente es el concepto de que una máquina de Turing es una persona 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 trabajodenominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un sí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...