4

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 !

Maman
  • 3,300
  • 1
    I don't have any background in computability, but wouldn't $g$ need to solve the halting problem? It seems like to determine its output, it needs to know if program $i$ halts on input $x$. – Joe May 18 '22 at 12:33
  • 1
    @Joe I think your idea is relevant ! Maybe it could be useful to work with the universal function $\varphi_i$ (probably with parametrization's theorem) before $g$ ! I try to think about it. – Maman May 18 '22 at 13:00
  • Hint: Let $c$ be such that $\varphi(c,j) = 0$ for all $j.$ Let $s$ be a recursive function such that $\phi(s(i),j) \simeq \phi(i,j)+1$ for all $i$ and $j$ (where $X \simeq Y$ means that either $X$ and $Y$ are both defined and equal, or they are both undefined). What is the value of $g(c,s(j),x)?$ – Mitchell Spector May 19 '22 at 08:03
  • @MitchellSpector It seems that we will get $g(c, s(j), x) = f(c, s(j),x)= \varphi_{s(j)}(x)=\varphi_{s(j)}(x)+1$. Hence $ \varphi_{s(j)}(j)=\varphi_{j}(j)+1$ however by Kleene's fixed point theorem we get that $\varphi_{s(j)}= \varphi_j$ which gives that $\varphi_j(j) = \varphi_j(j)+1$. I guess it would be valid if $W_j$ and $W_{s(j)}$ are equal ? So perhaps we have to justify that the total recursive function $s$ is such that "$\forall x (W_j = W_{s(j)} \land (\varphi_{s(j)}(x) \downarrow \ \rightarrow \varphi_{s(j)}(x)\neq 0))$ ? – Maman May 19 '22 at 11:25
  • The formula you wrote for $g(c,s(j),x)$ is right if $\varphi_j(x)$ converges. But if $\varphi_j(x)$ diverges, then $g(c,s(j),x)=\varphi_c(x)=0.$ So if $g$ were recursive, then you could solve the halting problem recursively: $\varphi_j(x)$ converges iff $g(c,s(j),x)\neq 0.$ – Mitchell Spector May 19 '22 at 17:02
  • @MitchellSpector Shouldn't it be : if $\varphi_{s(j)}(x)$ converges, then after, if $\varphi_{s(j)}(x)$ diverges ? – Maman May 19 '22 at 19:09
  • 1
    I wrote up the details as an answer below. – Mitchell Spector May 20 '22 at 04:16

2 Answers2

2

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.

Mitchell Spector
  • 9,917
  • 3
  • 16
  • 34
  • 1
    Thank you for the complete answer ! Why can we consider such a $c$ here ? Is this because the function which is always $0$ is recursive ? Moreover I have the feeling that your total recursive function $s$ checks that $\forall j \in \omega \ (\varphi_i(j) \downarrow \ \Leftrightarrow \varphi_{s(i)}(j) \downarrow \land \ (\varphi_{s(i)}(j) \downarrow \ \Rightarrow \varphi_{s(i)}(j)>0))$ ? Finally what is concretely the difference between the $f$ of the hint and the $g$ of the statement ? – Maman May 21 '22 at 16:39
  • 1
    Yes, the constant zero function is recursive, so it must have an index. Call it $c.$ – Mitchell Spector May 21 '22 at 16:41
  • 1
    As for $s,$ you can think of it in terms of algorithms (or Turing machines). If $j$ is the index of some algorithm, then $s(j)$ is the index of the algorithm which starts by executing the algorithm $j$ and then, if it halts, adds $1$ to $j$'s output. – Mitchell Spector May 21 '22 at 16:42
  • I recommend looking at my other answer; I think I prefer that approach. – Mitchell Spector May 21 '22 at 16:44
  • I know that the s-m-n part is correct for the function $s$. Here is my suggestion : let us say that I consider $\psi(i,j) = 1$ if $x \in W_i$ and $\uparrow$ otherwise. Hence $\psi$ is recursive, so there exists an index $k$ such that : $\psi_k(i,j)= \varphi^2(k,i,j)= \varphi(s_{1}^{2}(k,i),j)$ by s-m-n. Hence $s_{1}^{2}(k,i)=s(i).$ – Maman May 21 '22 at 16:46
  • You also asked what the difference is between $f$ and $g$. $f(i,j,x)$ is defined only when both $\varphi(i,x)$ and $\varphi(j,x)$ are defined. In contrast, $g(i,j,x)$ is defined if either (or both) of $\varphi(i,x)$ and $\varphi(j,x)$ are defined. – Mitchell Spector May 21 '22 at 16:48
  • 1
    Ok that was I was thinking but I thought it was to simple to be the answer... – Maman May 21 '22 at 16:49
  • 1
    But I haven't thought about what the hint regarding $f$ was intended to point you to. Maybe there's some different way of arranging things that explicitly uses the function $f.$ – Mitchell Spector May 21 '22 at 16:56
1

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.

Mitchell Spector
  • 9,917
  • 3
  • 16
  • 34