Is the proof of the uncomputability of the following function correct? Let the following function be given:
$f(x) = \begin{cases} 1 & \mbox{if } \forall n \Phi_x(n+1) \uparrow \mbox{ or } \Phi_x(n+2) \uparrow \\
\uparrow & \mbox{otherwise}
\end{cases}$
Define an auxiliary function $h$ as follows:
$h(x,y) = \begin{cases} 1 & \mbox{if } y = 0 \mbox{ or } \Phi_x(x) \downarrow \\
\uparrow & \mbox{if } y > 0 \mbox{ and } \Phi_x(x) \uparrow 
\end{cases}$
Since $h$ is computable, there is an index $i$ s.t. $\Phi_i(x,y) = h(x,y)$ $\forall x,y \in \mathbb{N}$. By the s-m-n theorem we have $\Phi_{s(i,x)}(y) = \Phi_i(x,y)$. Due to $s(i,x)$ being total and computable, it follows from the fixed-point theorem that there is some $p \in \mathbb{N}$ s.t. $\Phi_{l(p)} = \Phi_p$, where $l(x) = \lambda x.s(i,x)$.
Now, assume that $f$ is computable, then
$f(p) = \begin{cases} 1 & \mbox{if } \forall n \Phi_p(n+1) \uparrow \mbox{ or } \Phi_p(n+2) \uparrow \\
\uparrow & \mbox{otherwise}
\end{cases}$
$\ = \begin{cases} 1 & \mbox{if } \forall y \Phi_p(y+1) \uparrow \\
\uparrow & \mbox{otherwise} \end{cases}$
$\ = \begin{cases} 1 & \mbox{if } \Phi_p(p) \uparrow \\
\uparrow & \mbox{otherwise} \end{cases}$
If $f$ were computable, then the complement of the halting problem would be recursively enumerable. Contradiction!
 A: I don't understand your last computation of $f(p)$. First, note that $p$ is a fixed value, which is special because it has the property that $l(p)=p$. These values are called fixed points of the functions, but they're not necessary for the solution, because if you try to compute $f(p)$, it will give you just the value of $f$ on the specific point $p$. But you need to end up with a function that will result to be the halting problem, not just a particular value of the function. In order to do this, you have to use the fact that $$\Phi_{l(x)}(n)=\Phi_{s(i,x)}(y)=\Phi_i(x,n)=h(x,n).$$
(You can also see at your other question that Magdiradag computed $h(s(i,x))$, which is $h(l(x))$ and he showed that this function is the halting problem.)
So, you have that
\begin{align}
f(l(x))&=\begin{cases}1,\text{ if }\forall n(\Phi_{l(x)}(n+1)\uparrow\text{ or }\Phi_{l(x)}(n+2)\uparrow)$ \\ \uparrow,\text{ else}\end{cases}\\
&=\begin{cases}1,\text{ if }\forall n(h(x,n+1)\uparrow\text{ or }h(x,n+2)\uparrow)$ \\ \uparrow,\text{ else}\end{cases}
\end{align}
But note that the condition $\forall n(h(x,n+1)\uparrow\text{ or }h(x,n+2)\uparrow)$, is equivalent to $\forall n(n+1>0\text{ or }n+2>0)$ (which is true anyway) and $\Phi_x(x)\uparrow$. So, you get
\begin{align}
f(l(x))&=\begin{cases}1,\text{ if }\Phi_x(x)\uparrow \\ \uparrow,\text{ else}\end{cases}=\text{HP}
\end{align}
