Maquinas De Turing

Departamento de Ingeniería Informática y Computación
Universidad de Tecnológica Metropolitana
Santiago-Chile.

Máquinas de Turing

Mario Ibarra, Abraham Muñoz

Una Máquina de Turing es un modelo matemático que consiste en un autómata capaz de implementar cualquier problema matemático expresado por medio de un algoritmo.
En el concepto de las máquinas de Turing encontramos problemas dediversas complejidades y en los problemas que no tienen un tiempo de resolución polinomial.

El uso de las máquinas de Turing se aplica a problemas de decisión, es decir problemas cuya respuesta sea sí o no, a pesar que su campo se extiende a problemas de optimización, tal como si existe un camino Hamiltoniano de longitud menor o igual a k.
En una máquina de turing determinística (DTM) debemosrecordar que su complejidad está dada por la cantidad de movimientos de la cabeza en función del tamaño de la entrada y que un problema está en P si existe una DTM de complejidad polinomial que lo resuelva, hay que tener en cuenta que para que una DTM resuelva un problema P lo tiene que hacer en tiempo lineal.
En el mundo de los problemas resolubles por una máquina de turing existen diversos tiposde problemas tales como los p, p-completos, np, np-Hard.
El objetivo de este paper es mostrar como los problemas np son derivados por una máquina de turing.

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ónestá completamente determinada por un conjunto finito de instrucciones elementales.
Formalmente, Una máquina de Turing es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente #, ó 0), unconjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal yescribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

Dónde: (Pérez, 2005)*  es un conjunto finito de estados.
*  es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
*  es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta ().
*  es el estado inicial.
*  es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
*  es elconjunto de estados finales de aceptación.
*  es una función parcial denominada función de transición, donde  es un movimiento a la izquierda y  es el movimiento a la derecha.
Una vez definida lo que es una máquina de Turing, se expondrá sobre los tipos de problemas con resolución en tiempo polinomial y no polinomial. (Alonso)
Dentro del universo de los problemas NP, nos encontramos conproblemas P y los NP- completos
Para ser resueltos estos problemas existen diversas máquinas de turing tales como las DMT(Maquina de Turing Determinista) y NDTM(Maquina de Turing no determinista), una DTM como máquinas de Turing con varias cinas, o random Access pero que tan solo pueden probarse que son equivalentes en términos de polinomialidad de los problemas de las DTM.
Al existir las DTM,...