4
$\begingroup$

the following function was shown not to be computable:

$h(x) = \begin{cases} \mu n.\Phi_x(n) \downarrow & \mbox{if } \exists n \Phi_x(n) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$

using the following auxiliary function:

$f(x,y) = \begin{cases} 0 & \mbox{if } y > 0 \mbox{ or } \Phi_x(x) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$

My question is now: what is the reason behind choosing this particular auxiliary function? I am not quite sure about the role of the $y > 0$.

Thanks.

$\endgroup$
  • $\begingroup$ Can you tell us the argument, using $f$, that shows that $h$ is non-computable? Whatever it is, the point is probably that, for a given $x$, the smallest $y$ such that $f(x, y) \downarrow$ is $0$ if $\Phi_x(x) \downarrow$ and $1$ if $\Phi_x(x)\uparrow$. $\endgroup$ – Magdiragdag Mar 11 '14 at 19:57
  • $\begingroup$ Thanks for your response. The problem is that I only have some lecture notes, which may not be complete. What I additionally have is the following: $f$ is assumed to be computable, hence there is an index $i$ s.t. $\Phi_i = f$. From the s-m-n theorem we get that $\Phi_i(x,y) = \Phi_{s(i,x)}(y)$. We let $l(x) = s(i,x)$, since $i$ is fixed in $s(i,x)$. Then from the fixed-point theorem it follows that there is a $p$ s.t. $\Phi_{l(p)} = \Phi_p$. This means $f(x,y)$ can be rewritten as $\Phi_p(y)$. From this it should follow that if the function were computable, we could solve the halting problem. $\endgroup$ – trojan Mar 11 '14 at 20:05
2
$\begingroup$

Let me first prove that $h$ is not computable and then try to motivate the choice of $f$.

First of all note that the function $f$ is computable (Intuition: if $y > 0$, then output $0$; otherwise, start computing $\Phi_x(x)$; if that never terminates, then the computation of $f$ doesn't terminate either; if the computation of $\Phi_x(x)$ terminates, then output $0$.)

As in the comment by the OP, let $i$ be an index of $f$, i.e., $f = \Phi_i$; By the s-m-n theorem, $f(x,y) = \Phi_i(x,y) = \Phi_{s(i,x)}(y)$ for all $x, y$.

Now suppose that $h$ is computable. Then so would be the function $\lambda x.h(s(i,x))$. However $$\begin{align*} h(s(i,x)) & = \begin{cases} \mu y.\Phi_{s(i,x)}(y) \downarrow & \text{if such a $y$ exists} \\ \uparrow & \text{otherwise} \end{cases} \\ & = \mu y. f(x,y)\downarrow \qquad \text{(note that such a $y$ always exists)} \\ & = \begin{cases} 0 & \text{if } \Phi_x(x) \downarrow \\ 1 & \text{if } \Phi_x(x)\uparrow. \end{cases} \end{align*}$$ So, this would allow you to decide whether or not $\Phi_x(x)\downarrow$, giving a contradiction.

To give some motivation for the choice of $f$, note that although the function $g$ defined by $$g(x) = \begin{cases} 0 & \text{if $\exists n. \Phi_x(n) \downarrow$} \\ \uparrow & \text{otherwise} \end{cases}$$ is computable, finding the smallest $n$ for which $\Phi_x(n) \downarrow$ is not computable.

(Intuition: you can compute $g$ by interleaving the computations of $\Phi_x(0)$, $\Phi_x(1)$, $\dots$. If one of those ever terminates, then output $0$; if they all never terminate, then neither does the computation of $g$. For $h$ this trick doesn't work, because even if, say, the computation of $\Phi_x(100)$ terminates, you'll never know if you should output $100$ or wait until one of the computations of $\Phi_x(0)$, $\dots$, $\Phi_x(99)$ terminates.)

So what $f$ is doing is making sure that the computation of $f(x,1)$ always terminates. However, you can't be sure that $1$ is the smallest $y$ for which the computation $f(x,y)$ terminates, because termination of the computation of $f(x,0)$ is equivalent to the termination of the computation of $\Phi_x(x)$, which is undecidable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much, this made the whole thing a lot more clear. Does the last equation of $h(s(i,x))$ come from the fact that $\mu y.f(x,y) \downarrow$ yields $0$ if $\Phi_x(x) \downarrow$ and otherwise $1$ is the smallest number for which $y > 0$ holds? $\endgroup$ – trojan Mar 13 '14 at 0:37
  • $\begingroup$ You're welcome. And, yes, indeed, that's indeed the reason for the last equality for $h(s(i,x))$. $\endgroup$ – Magdiragdag Mar 13 '14 at 5:02
  • $\begingroup$ alright, thanks again! :) $\endgroup$ – trojan Mar 13 '14 at 19:05
2
$\begingroup$

Theory

This is a variation of Rice's theorem, which says that if $C$ is a non-empty and proper subclass of the class of all recursive functions, then the set $\{x : \phi_x\in C\}$ is not decidable. Hence, the function $$g(x)= \begin{cases} 1,\text{ if }\phi_x\in C\\ 0, \text{ else} \end{cases}$$ is not computable.

A short application

We put $C$ to be the subclass of all functions $\phi_x$ such, that $h(x)\downarrow\Rightarrow \exists n.\phi_x(n)\downarrow$. Take $$k(x)= \begin{cases} 0,\text{ if } x>0\\ \uparrow,\text{ else } \end{cases}$$ We note that $k\in C$, because $k(1)\downarrow$, so $C$ is non-empty. Also, it is a proper subclass, since there is a partial recursive function that does not belong in $C$, namely the nowhere defined function $\Omega(x)=\uparrow$.

You can define $$ g(x)= \begin{cases} 1,\text{ if }h(x)\downarrow\\ 0,\text{ else } \end{cases} = \begin{cases} 1,\text{ if }\phi_x\in C\\ 0,\text{ else } \end{cases} $$ Then, by Rice's theorem, $g(x)$ is not computable. Then $h(x)$ is not computable either, because if it was, then $g$ would be computable too. But it's not because Rice's theorem says so.

A variant

If you don't want to use Rice's theorem, you can use a variation of its proof. Here we put $C$ to be the subclass of all partial recursive functions for which $\exists n.\phi_x(n)\downarrow$. So actually $C$ is the same as above and we already have found a $k\in C$.

So now, we note that $$h(x)= \begin{cases} \mu y.\phi_x(y)\downarrow,\text{ if }\exists n.\phi_x(n)\downarrow\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.\phi_x(y)\downarrow,\text{ if }\phi_x\in C\\ \uparrow, \text{ else} \end{cases}$$ is quite similar to $g$ defined above. We assume it is computable. The proof of Rice's theorem uses a computable function $f(x,y)$ defined with the help of some computable $k\in C$. Then, he does some manipulations (which involve the S-n-m theorem) and concludes that $g$ composed with another decidable function decides the halting problem. This is a contradiction since the halting problem is not decidable, hence $g$ is not computable. We will use a similar method for $h$ instead of $g$.

So, let $$f(x,y)= \begin{cases} k(y), \text{ if }\phi_x(x)\downarrow\\ \uparrow,\text{ else} \end{cases} = \begin{cases} 0, \text{ if }y>0\text{ or }\phi_x(x)\downarrow\\ \uparrow,\text{ else} \end{cases}$$ Note that this is the function on your post and it is computable. The role of $y>0$ is that we need to use some function from subclass $C$. And we found such a function $k\in C$, which uses the case $y>0$. By the S-n-m theorem there is a primitive recursive (meaning, computable) function $l(x)$ such, that $f(x,y)=\phi_{l(x)}(y)$. Let's see what's happening when trying to compute $h(l(x))$ which is assumed to be computable. $$ h(l(x))= \begin{cases} \mu y.\phi_{l(x)}(y)\downarrow,\text{ if }\exists n.\phi_{l(x)}(n)\downarrow\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\exists n.f(x,n)\downarrow\\ \uparrow, \text{ else} \end{cases} =\\= \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\exists n.(f(x,n)=k(n))\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\phi_x(x)\downarrow\\ \uparrow, \text{ else} \end{cases} =\text{HP} $$ So you have in your hands a function that decides the halting problem, namely $h\circ l$. This is a contradiction. So, $h\circ l$ is not computable. But you know that $l$ is, so the wrong assumption leading you to contradiction was that $h$ is computable.

| cite | improve this answer | |
$\endgroup$

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.