Search code examples
computation-theory

Checking whether a function is computable or not

I've been given the following function written in pseudocode:

P:

{ 

int x, y, z;
read (x, y, z); 
while (x != y) {
   x = x - y;
   z = z + y
}; 
write z; 

}

Given that f(x,y,z) is the function calculated by P, I would like to know if the function "g(x,y,z)=1 if f(x,y,z) is not a total function or g(x,y,z)=0 otherwise", is computable.

My first guess is: yes, it is computable (for example for x=y).

Is there a more rigorous general approach to prove that?

Solution

  • P does not change the value of y, and the only way it changes the value of x is to subtract y from x until x = y. If subtracting y from x does not eventually result in x = y, then the loop continues forever. We know that subtracting y from x repeatedly can only cause x = y if initially x = cy for natural numbers c >= 1. So, g(x,y,z) = 1 because f(x,y,z) is not a total function; it is undefined when x != cy for any natural number c >= 1. Even if what you meant is that g(x,y,z) = 1 whenever f(x,y,z) is defined, it is still computable, since g(x,y,z) is the function:

    g(x,y,z) = { 1, if x = cy for some natural number c >= 1 }
           { 0, otherwise                                }

    The condition x = cy for some natural number c >= 1 is itself computable since this is equivalent to "x >= y" and "GCD(x, y) = y".