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$

1 Answer 1

3
$\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$
9
  • 2
    $\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$ Apr 24, 2018 at 22:14
  • 2
    $\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$ Apr 24, 2018 at 22:15
  • 2
    $\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$ Apr 24, 2018 at 22:17
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Halting_problem. $\endgroup$ Apr 24, 2018 at 22:24
  • 2
    $\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$ Apr 24, 2018 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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