1

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!

trojan
  • 79

1 Answers1

1

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}

Community
  • 1
frabala
  • 3,732
  • 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. – trojan Mar 17 '14 at 13:55
  • @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. – frabala Mar 17 '14 at 18:12
  • I edited the answer to include this. – frabala Mar 17 '14 at 18:36
  • 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). – trojan Mar 17 '14 at 18:42
  • @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... – frabala Mar 18 '14 at 03:56
  • I am also not yet sure about the $f(p)$ thing, maybe it works only in some special cases. However, I think now that the approach with $f(l(x))$ shows what is going on anyway. So, thank you again for your help! – trojan Mar 21 '14 at 15:14