Introducción


La Máquina de Turing, presentada por Alan Turing en 1936 es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos. Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).

File:Alan Turing cropped.jpg
Estatua De Alan Turing



Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control). Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora (problema indecidible) a notación de las máquinas de Turing es sencilla y exacta, por lo que es más cómodo trabajar con ellas a la hora de estudiar qué problemas son decidirles (P) y cuáles indecibles (NP). Por el momento la relación de inclusión entre P y NP está por demostrar, aunque sí sabemos que

P⊆NP


Comentarios

Publicar un comentario

Entradas populares de este blog

Proceso

Imagen
Lograron Resolver el Ejercicio Anteriormente Planteado? vamos a ver el proceso de la resolución del mismo ejercicio Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s). Solución: Si el Algoritmo Recorre la cinta de izquierda a derecha,   lo vamos a ir sustituyendo 1’s por 0’s y viceversa Definición de la MT Necesitamos implementar una Máquina de Turing que se comporte como transductor, porque genera una salida en la cinta. Tendremos un solo estado, que será el inicial, q0, sobre el que se realizan todas las transiciones MT1 =({0,1},{0,1,},,{q0},q0,f,{Φ}), donde f Si además se exige que el transductor termine en un estado final y pare, si la entrada es correcta, es decir, una simple secuencia de ceros y unos, la solución sería: MT1.2 = ({0,1},{0,1,},,{q0,q1},q0,f,{q1}), donde f Si además del estado final se exige que la cabeza de la...
Leer más

Tarea

Un ejercicio Propuesto que me gustaria Dejarles para que practiquen Maquina de Turing es la siguiente Diseñar una Máquina de Turing que calcule el complemento a 1 de un número binario. (Es decir, que sustituya los 0’s por 1’s y los 1’s por 0’s). 
Leer más

Evaluación

Después de ver un ejemplo de un ejercicio de maquina de turing y también ver con los procedimiento como se resuelve. les pondré unos ejercicios propuesto con evaluación cada uno 1) Diseñar una Máquina de Turing que obtenga el sucesor de un número en codificación unaria. Considerar en la codificación unaria que el 0 se representa por la cadena vacía, el 1 por 1, el 2 por 11, etc. 5pts 2) Diseñar una Máquina de Turing que obtenga el predecesor de un número en codificación unaria. Considerar la codificación unaria del 0 igual que en el ejercicio 1 5pts 3) Diseñar una Máquina de Turing que calcule la paridad de un número binario. Es decir, si el número de 1’s de la cadena es par, se añade un 0 al final, y si es impar, se añade un 1. 5pts 4) Diseñar una Máquina de Turing que haga una copia de una cadena de símbolos {A,B,C}. Por ejemplo, para la entrada “bAABCAb” devuelve en la cinta “bAABCAAABCAb”, donde ‘b’ representa el blanco. 5pts ...
Leer más