Maquina De Turing

4MS
UNIDAD:
KARIME LOPEZ PUERTO
4MS
UNIDAD:
KARIME LOPEZ PUERTO
INSTITUTO TECNOLÓGICO DE MÉRIDA

11
MAQUINA DE TURING
TEORIA DE LA COMPUTACION
DIEGO PANTI LINARES

INSTITUTO TECNOLÓGICO DE MÉRIDA

11
MAQUINA DE TURING
TEORIA DE LA COMPUTACION
DIEGO PANTI LINARES

MAQUINA DE TURING
DEFINICION.-Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal dedatos.  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 escribir nuevos datos en la secuencia;  recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito deestados posibles.
HISTORIA:
El concepto de Máquina de Turing fue 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 las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse acualquier 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 este modelo teórico y el análisisde 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 determinismo respectivamente de la máquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posiblecrear 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.
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 determinadosólo una parte finita es accesible.

MAQUINA DE TURING:
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 muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchasversiones 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 de lectura/escritura.  La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo deun 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 como sean 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 exige ningún estado especial con el que sea iniciada la máquina.
* Existe una tabla de acción , que contiene las instrucciones de lo...