Why this partial function is not computable?

Question

Let us consider the following function : $g(i,j,x) = \left\{ \begin{array}{ll} \varphi(i,x) \lor \varphi(j,x) & \mbox{if} \ \varphi(i,x) \downarrow \land \ \varphi(j,x)\uparrow \ \mbox{or} \ \varphi(i,x)\uparrow \land \ \varphi(j,x) \downarrow. \\ \sup(\varphi(i,x), \varphi(j,x)) & \mbox{if} \ \varphi(i,x) \downarrow \land \ \varphi(j,x)\downarrow. \\ \ \uparrow & \mbox{otherwise}. \end{array} \right.$

where $\varphi$ stands for the universal computable function (for one argument here) and $\sup$ is the recursive primitive function which takes the maximum of two integers.

I have to show that $g$ is not computable. The hint suggested is to focus on the partial function $f:(i,j,x)\mapsto \sup(\varphi(i,x), \varphi(j,x))$.

I really do not know how to start. For instance, in a first time, I do not see differences between $f$ and $g$.

Thanks in advance !

Answer 1

First, the use of the notation $\lor$ in the first line in the definition by cases of the function $g$ is something I haven't seen before, but I'm presuming the definition means:

$$g(i,j,x) = \begin{cases} \varphi(i,x), & \text{if } \varphi(i,x) \downarrow \;\land \;\;\varphi(j,x) \uparrow ,\\ \varphi(j,x), & \text{if } \varphi(i,x) \uparrow \;\land \;\;\varphi(j,x) \downarrow ,\\ \sup(\varphi(i,x), \varphi(j,x)), & \text{if } \varphi(i,x) \downarrow \;\land \;\;\varphi(j,x) \downarrow ,\\ \uparrow, & \text{otherwise}. \end{cases}$$

Let $c$ be an index for the recursive function that is always $0;$ for all $j\in\omega,$ $$\varphi(c,j) = 0.$$

By the s-m-n theorem, there exists a recursive (in fact, a primitive recursive) function $s$ such that, for all $i, j\in\omega,$ $$\varphi(s(i),j) \simeq \varphi(i,j)+1$$ (where $X \simeq Y$ means that either $X$ and $Y$ are both defined and are equal, or they are both undefined).

Let $g$ be as in the problem statement. For all $j,x\in\omega,$ consider the value $g(c, s(j), x):$

$$g(c,s(j),x) = \begin{cases} \varphi(c,x), & \text{if } \varphi(c,x) \downarrow \;\land \;\;\varphi(s(j),x) \uparrow ,\\ \varphi(s(j),x), & \text{if } \varphi(c,x) \uparrow \;\land \;\;\varphi(s(j),x) \downarrow ,\\ \sup(\varphi(c,x), \varphi(s(j),x)), & \text{if } \varphi(c,x) \downarrow \;\land \;\;\varphi(s(j),x) \downarrow ,\\ \uparrow, & \text{otherwise}. \end{cases}$$

The value $\varphi(c,x)$ converges (to $0$) for all $x,$ so cases 2 and 4 above can't happen. Also, $\varphi(s(j),x)$ converges iff $\varphi(j,x)$ converges, and the formula simplifies to:

$$g(c,s(j),x) = \begin{cases} 0, & \text{if } \varphi(j,x) \uparrow ,\\ \sup(0, \varphi(s(j),x)), & \text{if } \varphi(j,x) \downarrow .\\ \end{cases}$$

Using the basic property of the function $s$ (and the fact that $0$ is the smallest number), we have:

$$g(c,s(j),x) = \begin{cases} 0, & \text{if } \varphi(j,x) \uparrow ,\\ \varphi(j,x)+1, & \text{if } \varphi(j,x) \downarrow .\\ \end{cases}$$

So $\varphi(j,x)$ converges iff $g(c,s(j),x) \neq 0.$ But that means that $g$ can't be recursive; if $g$ were recursive, this would give a computable way to solve the halting problem.

Answer 2

Here's a different, simpler proof:

Let $A$ be any recursively enumerable, non-recursive set. (For example, you can set $A = \{x \mid \varphi(x,x)\downarrow \}.)$

Then $$\psi(x)=\begin{cases}1, &\text{if }x\in A,\\ \uparrow, &\text{if }x\notin A,\end{cases}$$ defines a partial recursive function $\psi, $ so there is an index $e$ such that $$\varphi(e,x)\simeq\psi(x)$$ for all $x.$

Let $c$ be an index for the constant-zero function: $$\varphi(c,x)=0$$ for all $x.$

Then $$g(c,e,x)=\begin{cases}1,&\text{if }x\in A,\\0,&\text{if }x\notin A,\end{cases}$$

which would contradict the non-recursiveness of $A$ if $g$ were recursive.

---

Not only is this method a little simpler than the one in my other answer, it also generalizes better. For example, if you replace "sup" in the problem with "inf", this solution can easily be modified to handle that, by just switching the $0$s and $1$s in the proof.