Proceso

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 pila termine al inicio de la palabra (para que se pueda ver el contenido de la cinta en la herramienta Jflap), se obtiene la siguiente máquina de Turing

MT1.3 =({0,1},{0,1,},,{q0,q1,q2},q0,f,{q2}), donde f