Proyecto De Eletronica

Laboratorio Practico de Maquinas de Turing

1. 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).

2. 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.

3. 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 2.

4. 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.

DESARROLLO:

1. Se tiene que recorrer la cinta de izquierda a derecha, cambiando los 1’s por 0’s y viceversa.

En la implementación de la máquina de turing tendremos un estado q0 y en el tenemos que realizar las transiciones.

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

2. La representación de un número en unario, según las indicaciones del enunciado es:

n => n+1 “unos”

(decimal) (unario)

Así:

0 => cadena vacía

1 => 1

2 => 11

3 => 111

4 => 1111

5 => 11111

…

Sucesor: Recorrer número hasta el final [transición recursiva en q0], y allí añadir un 1 adicional, a la derecha de la secuencia de 1’s [transición de q0 a q1].

MT2=({1},{1, •},•, {q0,q1},q0,f,{q1}), donde f:

3. Predecesor unario: Recorrer número hasta el final [transición recursiva en q0], situarse en el último dígito [transición q0 a q1, moviendo puntero a la izquierda], y escribir un blanco encima para borrarlo [transición q1 a q2].

Definición de la MT

MT3.1=({1},{1, •}, •,{q0,q1,q2},q0,f,{q2}), donde f

Codificación unaria: el cero se representa por la palabra vacía y el número entero “n” por una secuencia de “n” consecutivos.

Se recorre el número hasta llegar al final, i.e. una celda vacía posterior al último 1.

Al

...