Conjunto Mínimo de Instrucciones:

Como ya bien sabemos el Lenguaje While consta de cuatro instrucciones de asignación:

Xi:=Xj

Xi:=Xj + 1

Xi:=Xj – 1 ( 0 -1 = 0)

Xi:=0

La primera pregunta que debemos plantearnos es si dicho  juego de instrucciones es mínimo.Para ello, debemos ver si es posible implementar alguna instrucción con el resto de la sintaxis del lenguaje o bien demostrar que esto no es posible.

×Veamos la instrucción Xi:=0 :

×Esta instrucción puede realizarse fácilmente con el bucle indefinido y con la instrucción de decrementar de la siguiente manera:

while Xi ¹ 0 do

Xi:=Xi-1

od

×Aunque es preferible la realización anterior, otra posible simulación podría ser la siguiente:

Dentro de la Semántica Informal vimos que aquellas variables que no son de entrada se inicializan implícitamente a cero.Por lo que existe la posibilidad de obtener el cero mediante la asignación de la variable Xi , que es a la que queremos dar el valor nulo, a la variable Xj con j = p+1.Siendo Xj una variable que sabemos con total seguridad que no ha sido utilizada aún.Pues ‘p’ es el número total de variables utilizadas por el programa en el instante que realizamos la asignación Xi:=Xj.

Ya estamos en disposición de poder asegurar que el juego de instrucciones del que consta el Lenguaje While no es mínimo.Quedando nuestro juego de instrucciones como sigue:

Xi:=Xj

Xi:=Xj + 1

Xi :=Xj– 1 ( 0 -1 = 0)

La siguiente cuestión que debemos plantearnos es si este conjunto de instrucciones ya es mínimo o puede reducirse todavía más.

×Veamos la instrucción Xi:=Xj :

×Esta instrucción puede realizarse con la utilización de las instrucciones de incremento y decremento de la siguiente manera:

while Xi ¹ 0 do

Nos aseguramos Xi:=Xi-1

que X_i valga 0. od

while Xk ¹ 0 do

Nos aseguramos Xk:=Xk-1 Utilizamos X_k para que la asignación no sea destructiva, es decir,

que X_k valga 0. od para que el valor de X_j no se pierda.

while Xj ¹ 0 do

Xj:=Xj-1;

Xi:=Xi+1;

Xk:=Xk+1

od

while Xk ¹ 0 do

Xk:=Xk-1; Con este bucle devolvemos a Xj su valor.

Xj:=Xj+1

od

Nuestro conjunto de instrucciones queda como sigue:

Xi:=Xj + 1

Xi :=Xj – 1 ( 0 -1 = 0)

× Restricción del conjunto encontrado:

Podemos restringir todavía más el conjunto encontrado estableciendo que las instrucciones con las que vamos a trabajar son:

Xi:=Xi + 1

Xi :=Xi – 1 ( 0 -1 = 0)

Así realizamos la simulación de Xi:=Xj-1 como sigue:

(1, 2, programa)

programa: Xj:=Xj-1

while Xj ¹ 0 do

Xi:=Xi+1; Con Xi como variable auxiliar

Xj:=Xj-1

od

Y la simulación de Xi:=Xj + 1 como sigue:

(1, 2, programa)

programa: Xj:=Xj+1

while Xi ¹ 0 do

Xi:=Xi-1; Con Xj como variable auxiliar

Xj:=Xj+1

od

Este es el conjunto de instrucciones más pequeño que he encontrado.Lo cual no significa que no pueda reducirse todavía más.

Volver.