PROCESO

Links para adquirir los conocimientos necesarios y poder elaborar la tarea anteiormente planteada

https://www.youtube.com/watch?v=dIVgs0rpcqQ

https://www.youtube.com/watch?v=NS-NQ5mCSs8

https://www.youtube.com/watch?v=NS-NQ5mCSs8

Ejemplo:

Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1.

Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número.

Vamos a considerar tres estados:

q0,q1,q2$$q_0,q_1,q_2$$$${\mathrm{<br>}}_{}$$

·         Inicialmente, la MT está en el estado q₀ con la cabeza señalando la primera cifra del número.

La MT recorre todo el número para ver si es par o impar sin modificar su cinta.

δ(q0,0)=(q0,0,R)$$\delta (q_0,0)=(q_0,0,R)$$

δ(q0,1)=(q0,1,R)$$\delta (q_0,1)=(q_0,1,R)$$$$<br>$$

·         Notemos que, por ahora, la MT se detiene al llegar al primer símbolo en blanco a la derecha del número.

La MT vuelve a la anterior casilla (último número). Si es un 0, lo cambia por un 1 y pasa al estado final que es q₂ . Para hacer esto usaremos el estado q₁ :

δ(q0,B)=(q1,B,L)$$\delta (q_0,B)=(q_1,B,L)$$

δ(q1,0)=(q2,1,R)$$\delta (q_1,0)=(q_2,1,R)$$$$<br>$$

·         Si el número es impar, la MT no ha cambiado el último número, pero está en el estado q₁ . Tiene que cambiar todos los 1's consecutivos que haya de derecha a izquierda.

δ(q1,1)=(q1,0,L)$$\delta (q_1,1)=(q_1,0,L)$$$$<br>$$

·         Por ahora, la MT se para cuando llega al primer 0 (de derecha a izquierda) ó en un símbolo en blanco. Si es un 0, lo cambia por un 1 y el proceso finaliza:

δ(q1,0)=(q2,1,L)$$\delta (q_1,0)=(q_2,1,L)$$$$<br>$$

(Hemos escrito un desplazamiento a la izquierda, pero esto no tiene importancia ya que la MT ha llegado al estado final).

·         Si lo que señala la cabeza es un blanco en vez de un 1, tiene que cambiarlo por un 1 y finalizar el proceso.

δ(q1,B)=(q2,1,L)$$\delta (q_1,B)=(q_2,1,L)$$$$<br>$$

Donde el cuadro representa el símbolo en blanco B.

Vamos a simular la MT para varias entradas. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).

Entrada: 000; Resultado esperado: 001.

Entrada: 0011; Resultado esperado: 0100

Entrada: 111; Resultado esperado: 1000.

Entrada: 1; Resultado esperado: 10.