Having the function:

$$f(y) = \begin{cases} \ 1 &\text{if }\forall n \Phi_y(n)=n\lor \Phi_y(n) \!\uparrow\\ \ 0 &\text{otherwise.} \end{cases}$$

By the rule of thumb it should not be computable. How to prove it formally? If it's computable, I assumed a function like this exists: $$g(y) = \begin{cases} \ 1 &\text{if $f$(y) = 1 }\\ \ 0 &\text{if $f$(y) = 0} \end{cases}$$

I assumed $g(y)$ is computable. Now there exists a function $\Phi_{x_0}(x_0)$ which simulates $g(y)$. This means: $\Phi_{x_0}(x_0) \downarrow$ iff $\Phi_{x_0} (x_0) \uparrow$, which is a contradiction. Is this sufficient as a proof?

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 22 '17 at 14:55
  • $\begingroup$ Our reference question may be of help. $\endgroup$ – Raphael Jan 22 '17 at 14:55
  • $\begingroup$ I don't quite understand your proof. Try a reduction from the halting problem. $\endgroup$ – Yuval Filmus Jan 22 '17 at 15:41
  • $\begingroup$ So it's enough to show that we can map it onto the halting problem? I.e. having a set of instances of (A, D), where A is $\Phi_y(n)$ and D is some x from $N$, we get pairs in S such as ($\Phi_y$, 1), ($\Phi_y$, 2), ...., now H halts if $\Phi_y(n) $ = n. Thus we can map it onto the halting problem, therefore it's not computable? $\endgroup$ – TechCrap Jan 22 '17 at 16:00
  • $\begingroup$ Could you please provide a sample solution? So I could see the right way to go for exercises like this one. $\endgroup$ – TechCrap Jan 22 '17 at 16:03

Since I assume this is a homework question, I won't give a fully detailed proof but rather a sketch with some gaps to fill.

Consider the function $$g(x)= \begin{cases} x+1 & \text{ if } \varphi_x(x)\downarrow\\ \uparrow & \text{ otherwise}.\end{cases}$$ This function is computable (convince yourself of that!), so it has an index $e$.

Now consider the function $f$ on $e$, then computing $f(e)$ comes down to verifying whether $\forall n\ \varphi_e(n)\uparrow$. Can you see why this contradicts that the halting problem is not computable?

| cite | improve this answer | |
  • $\begingroup$ Thansk for the answer! Just to make it clear, this is not a homework assignment, it's already the exam preparation :). I see that the g(x) is computable, as we can construct a turing machine for each $\Phi_x(x)$ so that if it halts it gives back the answer. However if the $\Phi_e$ halts and gives back the answer, it also won't diverge as it will halt, right? Then f(e) gives back 0. However if $\Phi_e$ diverges we still assume f(x) to give back 1 which we can never decide? $\endgroup$ – TechCrap Jan 23 '17 at 21:15
  • $\begingroup$ To your first question, a computation either halts (converges) or it does not halt (diverges). So of course, if it halts, it won't diverge. $\endgroup$ – Dino Rossegger Jan 23 '17 at 21:34
  • $\begingroup$ And is the second question correct contradiction? :) $\endgroup$ – TechCrap Jan 23 '17 at 21:38
  • 1
    $\begingroup$ To your second question, $f(e)=1 \text{ if } \forall n\ \varphi_e(n)\uparrow$. This i ridiculous though, as it converges if another function diverges. $\endgroup$ – Dino Rossegger Jan 23 '17 at 21:43
  • $\begingroup$ One could also define $g$ more in the light of Yuval Filmus' answer, by $g(x)=\{x+1 \text{ if } \varphi_{x_0}(x_0)\downarrow\}$ for some natural number $x_0$. $g$ is again computable, say by $e$. Then we have solved the Halting problem as $f(e)=1$ if $\varphi_{x_0}(x_0)\uparrow$ and $f(e)=0$ if $\varphi_{x_0}(x_0)\downarrow$. I would accept both answers, although the one using this definition is maybe a little better as it shows better how to reduce the Halting problem to $f$. $\endgroup$ – Dino Rossegger Jan 23 '17 at 21:54

Here's how to solve the halting problem using $f$. Suppose that we are given a Turing machine $T$, and we want to know whether it halts on the empty input. Construct a Turing machine $T'$ which on input $n$ runs $T$, and if it ever halts, it outputs $n+1$. So $T$ halts on the empty input iff $f(\langle T' \rangle) = 0$.

Conversely, we can calculate $f$ using an oracle for the halting problem. Given a Turing machine $T$, construct a Turing machine $T'$ which runs $T$ on all possible inputs in parallel, and stops if it finds out that $T(n) \neq n$ for some $n$. Then $f(\langle T \rangle) = 0$ iff $T'$ halts.

What we have shown is that $f$ (more exactly, the set of 1-inputs of $f$) is $\Pi_1$-complete.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your answer! Unfortunately I can only accept only the single answer as a correct one! $\endgroup$ – TechCrap Jan 23 '17 at 22:59

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.