# Why is this function computable

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;
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?

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!).
• My formula for $g$ doesn't mention P. As a related example, suppose that $c(n) = \sum_{m=n+1}^\infty 2^{-m}$. Then $c(n) = 2^{-n}$ is computable, despite the fact that $c$ cannot sum the infinite series and see what it gets. – Yuval Filmus Apr 24 '18 at 22:14
• Nobody is forcing you to compute $g$ in a specific way. This is an obstacle that you're imposing on yourself for no reason. A function is just a mapping from input to output. Nothing more. – Yuval Filmus Apr 24 '18 at 22:15
• No, absolutely not. The way to think about is that $g$ is a function, not an algorithm. It has output $1$ if $x=ty$ for some integer $t \geq 1$, and it has output $0$ otherwise. How you implement $g$ is up to you. If you manage to find an algorithm that computes $g$, then it is computable. – Yuval Filmus Apr 24 '18 at 22:17
• You have a specific program $f$, for which the halting problem is computable. The halting problem for arbitrary programs is not computable. If you are still confused, I suggest asking a new question. – Yuval Filmus Apr 24 '18 at 22:31