Damiano Zanardini's Web page

Supongamos que Alice y Bob están implementando un sistema informático. Alice se encuentra con un fragmento de código P que quiere reutilizar, pero no está segura de lo que el código hace. Por esto pide a Bob que le diga lo que P calcula (Nota: este programa está escrito en el lenguaje usado por el analizador Interproc; se trata de una lenguaje muy sencillo que cualquier informático con conocimientos de algún lenguaje imperativo puede entender fácilmente):

proc p(a:int) returns (b:int)
begin
b = a*2;
end

var x:int, y:int;
begin
x = 20;
y = p(x);
end

Es muy fácil entender el resultado del cálculo de P, así que Bob puede contestar a la pregunta en pocos segundos y sin ninguna dificultad.

Ahora supongamos que Alice encuentra otro fragmento de código, Q, y, otra vez, quiere usarlo en su sistema. Para ello, pide a Bob que eche un vistazo a Q y le diga lo que calcula (Nota: para los que tengan dudas, "/" es la división entera y "%" es el resto):

proc p(a:int) returns (b:int)
var c1:int, c2:int, c3:int;
begin
c1 = a / 3;
c2 = a % 3 - 1;
b = c2;
c3 = c1;
while (c3>0) do
b = b + c3 % 3 + 2;
c3 = c3 - 1;
done;
if (c2 > 1) then
b = b + 2;
else
b = b + c2 + 1;
endif;
b = b + c1 * 3;
if (c1 % 3 == 2) then
b = b + c3;
else
b = b + 1;
endif;
end

var x:int, y:int;
begin
x = 20;
y = p(x);
end

Es evidente que entender lo que hace Q es mucho más difícil, así que Bob tarda un buen rato para contestar. Sin embargo, el resultado final es que... !`P y Q calculan exactamente lo mismo!

En general, Bob podrá con cualquier fragmento de código, y encontrará una respuesta para todas las preguntas que Alice le pueda poner. Lo malo es que podría tardar muchísimo (no sería muy difícil producir programas mucho más largos y complejos que sigan calculando la misma función). Por esto los informáticos intentan desarrollar unos programas, que llamaremos analizadores, que realicen el trabajo de Bob tardando mucho menos y con un mayor nivel de fiabilidad.

Lo que pasa es que ni siquiera el analizador más potente podrá contestar a todas las preguntas de Alice: siempre habrá un programa para el que no sabrá dar una respuesta (en este caso, que el valor final de "y" es 40).