Entradas

Conclusión

Imagen
Las máquinas de Turing son un esquema de suma importancia para el desarrollo de la informática moderna, gracias a ella se han establecido una infinidad de estándares de trabajo para todo desarrollador de software y ha permitido abstraer el comportamiento interno de la lógica de un sistema e incluso crear un modelo bajo el cual se puede desarrollar cualquier algoritmo imaginable (siempre y cuanto se considere una cantidad de memoria infinita para modelos hipotéticos). Sería imposible apreciar un campo tan amplio como lo es la informática sin los postulados producto de las máquinas de Turing y serán consideradas como uno de los pilares fundamentales de la informática moderna. Será necesario entonces, hacer del estudio de las máquinas de Turing un escalón de gran importancia en la formación de todo profesional que desee ejercer en las disciplinas vinculadas a la computación y su manejo se reflejará en una mayor internalización de conocimientos por parte de to...
Publicar un comentario
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 ...
Publicar un comentario
Leer más

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...
Publicar un comentario
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). 
Publicar un comentario
Leer más

Introducción

Imagen
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). 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,...
Publicar un comentario
Leer más