Máquina De Turing

Ingeniería en Informática
Secuencia: 3NV1
Departamento: Desarrollo Profesional Especifico
Coordinación: Academias de Computación
Asignatura: Teoría de la Computación
Alumno: Ramírez Bravo Juan C.

Instituto Politécnico Nacional

Unidad Profesional Interdisciplinaria de Ingeniería y Ciencias Sociales y Administrativas


Máquina de Turing

05/12/2011
Máquina de Turing (Conceptointroducido por Alan Mathison Turing en 1936)
¿Es posible encontrar una manera sencilla de decidir si un problema matemático cualquiera tiene solución?
Una máquina de Turing (parecida a un radiocasete) es un modelo matemático (conjunto de reglas que representan la explicación y la solución de un problema), que consiste en un autómata (máquina teórica) capaz de implementar (leer, interpretar)cualquier problema matemático (afirmación o interrogación a determinar si es verdadera o falsa) que se nos ocurra, con la única condición de que éste se pueda expresar por medio de un algoritmo, y cambia su estado en función de este.
Este autómata consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda.Consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba.

Realizando una analogía, podemos identificar el hardware de una computadora con la cabeza lectora y la cinta, mientras que el software serían las instrucciones de la cinta y la función de estado de la máquina de Turing.
Por tanto, una máquina deTuring permite comprender los límites de lo que podemos esperar que haga una Computadora y lo que no.
Cuando Alan Turing descubrió su máquina no lo hizo buscando la forma de inventar un ordenador personal (no era su principal motivación), sino tratando de resolver “el problema de la decisión”.
Alan Turing probó que cualquier método de implemetar un problema se puede siempre simplificar a unamáquina de Turing, es decir, su máquina era algo así como “la madre de todos los métodos”. También probó que no se puede construir una máquina de Turing capaz de determinar si un problema se va a poder resolver o no y, por tanto, quedó demostrado que no hay ningún sistema para decidir si un problema matemático tiene solución o no.

Máquina sencilla
Existen "variedades" de la máquina de Turing, pero lamás sencilla cumple las condiciones siguientes:
* Cuenta con una cinta sobre la que puede desplazarse un cabezal de lectura/escritura a la izquierda y a la derecha.  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 hayanescrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #).  La cinta puede contener tantas celdas como sean necesarias.
* 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 instruccionesde lo que hará el autómata.  Estas instrucciones representan en cierta forma el "programa" de la máquina.  Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos:
* Leer un carácter en la posición actual.
* Escribir un nuevo símbolo en esta posición (puede ser el mismo que había).  El símbolo a escribir es alguno del alfabeto de la máquina, y depende delcarácter leído y del estado actual.
* Desplazar el cabezal una celda a la derecha o a la izquierda;  en algunos modelos el desplazamiento puede ser nulo.
* Decidir cuál será el nuevo estado en función del carácter que se acaba de leer y del estado actual.  Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su...