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?