Maquina De Turing

Investigación Maquina de Turing

Investigación Maquina de Turing Unidad 2
Investigación Maquina de Turing Unidad 2
Instituto Tecnológico Superior de Lerdo

Curso Intensivo de Invierno 2012. Arquitectura de Computadoras

04/01/2013
Instituto Tecnológico Superior de Lerdo

Curso Intensivo de Invierno 2012. Arquitectura de Computadoras04/01/2013

Investigación Maquina de Turing
1. Marco teórico.
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentrode un computador.
Consistía en: una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otroslugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.

2. Desarrollo.
Alan Mathison Turing considerado uno de los padres de la ciencia de lacomputación siendo el precursor de la informática moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación
Alan Turing introdujo el concepto de máquina de 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 que se estudiaba la cuestión planteada por David Hilbertsobre 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, 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 uncomputador digital sea capaz de realizar.
Mediante este modelo 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 problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas,respectivamente. La máquina de Turing modela matemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta. La operación está completamente determinada por un conjunto finito de instrucciones elementales
una máquina de Turing consta de:
1. Una cinta que se divide en celdas,una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo especial llamado blanco (aquí escrito como 'B') y uno o más símbolos adicionales. La cinta se supone que es arbitrariamente extensible hacia la izquierda y hacia la derecha, es decir, la máquina de Turing siempre es suministrada con tanta cinta como necesite para su computación. Lasceldas que no se hayan escrito previamente se asumen que están rellenas con el símbolo blanco. En algunos modelos la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible hacia la derecha.
2. Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una (y sólo una) celda a la vez. En...