Why is this function computable

Question

I'm struggling to understand why this function is computable. This is the requirement:

Consider the following program P, written in a pseudo-C language:

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

Let $f(x, y, z)$ be the function computed by P. Is the following function g computable?

$g(x, y, z) = \begin{cases} 1 & f(x,y,z)\ halts \\ 0 & else \end{cases} $

Whenever I encounter a problem like this, I try to imagine a program that does exactly what $g$ does. In this case, a P2 program that checks if $f(x,y,z)$ halts.

Now, P halts if, basically, $x>y \ and \ y=1 $ or $x=y$ (there are probably more cases). In the other cases, P would just remain in the while loop, so $f$ is not total.

But how would P2 return $0$ if P wouldn't even halt? P2 would have to wait, and never return 0, so for some values the function is not computable, and x,y,z isn't always computable.

What am I thinking wrong here?

Answer 1

You can check that P halts iff $x = ty$ for some integer $t \geq 1$. Hence $g(x,y,z)$ is just the following function: $$ g(x,y,z) = \begin{cases} 1 & \text{ if $x = ty$ for some integer $t \geq 1$}, \\ 0 & \text{ otherwise.} \end{cases} $$ Given integers $x,y$, it is not hard to check whether $x = ty$ for some integer $t \geq 1$. Hence $g$ is computable (even in polynomial time!).