Showing that a function is not computable.

Question

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.

Answer 1

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.

Answer 2

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.