1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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!).

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:17
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Halting_problem. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '18 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.