1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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
    Commented Jan 22, 2017 at 14:55
  • $\begingroup$ Our reference question may be of help. $\endgroup$
    – Raphael
    Commented Jan 22, 2017 at 14:55
  • $\begingroup$ I don't quite understand your proof. Try a reduction from the halting problem. $\endgroup$
    – Yuval Filmus
    Commented Jan 22, 2017 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
    Commented Jan 22, 2017 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
    Commented Jan 22, 2017 at 16:03

2 Answers 2

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jan 23, 2017 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
    Commented Jan 23, 2017 at 21:34
  • $\begingroup$ And is the second question correct contradiction? :) $\endgroup$
    – TechCrap
    Commented Jan 23, 2017 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
    Commented Jan 23, 2017 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
    Commented Jan 23, 2017 at 21:54
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you for your answer! Unfortunately I can only accept only the single answer as a correct one! $\endgroup$
    – TechCrap
    Commented Jan 23, 2017 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.