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!


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}

| cite | improve this answer | |
  • $\begingroup$ Thanks for your answer. $f(p)$ follows from the fact that for any total computable function (here l(x)), there is some $p \in \mathbb{N}$ s.t. $\Phi_{l(p)}(y)= \Phi_p(y) = h(p,y)$. So I consider $f(p)$ to get, essentially, what you have defined with $f(l(x))$. If I understand your answer correctly, then the first part is basically the same as my solution. Correct me if I am wrong. $\endgroup$ – trojan Mar 17 '14 at 13:55
  • $\begingroup$ @trojan I understand how $p$ comes up in your solution, but it's not right to use it, because $p$ is just one value (fix point), while what you want to result to is a function on the domain of a variable, not on just one value. This function will result to be the halting problem. Also, a wrong thing is how you compute $f(p)$ to be the halting problem. For example, how from the condition $\forall n(\Phi_p(n+1)\uparrow\text{ or } \Phi_p(n+2)\uparrow)$ do you go to the condition $\forall y\Phi_p(y+1)\uparrow$? In your computation, you don't use that $\Phi_p(n)=f(p,n)$, while you should. $\endgroup$ – frabala Mar 17 '14 at 18:12
  • $\begingroup$ I edited the answer to include this. $\endgroup$ – frabala Mar 17 '14 at 18:36
  • $\begingroup$ I get your point with the function, but isn't it enough to have a contradiction with just one value, such that $f$ cannot be computable for an arbitrary $x$? I used this approach, because we also used the fixed point for another example in the lecture. The step from $\forall(\Phi_p(n+1)\uparrow)$ or $\Phi_p(n+2)\uparrow$ to $\forall y \Phi_p(y+1) \uparrow$ comes from the definition of $h$ and the fact that $\Phi_p(n) = h(p,n)$. Since for $y > 0$ the result is the same for $y+1$ and $y+2$ (I could have also used $n$ again). $\endgroup$ – trojan Mar 17 '14 at 18:42
  • $\begingroup$ @trojan You're right about the step. I didn't see it, until you explained. But about the $f(p)$ or $f(l(x))$ question, to be honest I got confused now, too :P Maybe your solution is correct after all! :P You could ask your professor, or maybe make a new question here. But clearly, computing $f(l(x))$ would suffice anyway... $\endgroup$ – frabala Mar 18 '14 at 3:56

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.