I have found the following task: Show that K (the halting set) is m-reducable to the zero functions $$ K \leq_M\{x | f_x = 0\}$$

We need to find a total-computable function h, such that: $$ x \in K \iff h(x) \in \{x | f_x = 0\} $$ The i have found this solution:

h(x,y) = t (if f_x (x)↓}

h(x,y) = ↑ (else)

But shouldn't h be a total-computable function? And h is not-total ? And why does it have two arguments? Any tips? Am I understanding things wrong?

page 5: http://www.cs.sjtu.edu.cn/~gao-xf/computability/Document/10-Reducibility.pdf


Your understanding is correct; the slides are somewhat confusingly written.

The function $f_{\bf 0}$ is not the desired $m$-reduction. Indeed it can't possibly be since the arity is wrong: an $m$-reduction is unary, but $f_{\bf 0}$ is binary. Instead, $f_{\bf 0}$ is an oddly-packaged description of the outputs of the intended $m$-reduction of $K$ to $\{x: \phi_x\simeq{\bf 0}\}$.

The point is that for each $x$, the function $$\eta_x: y\mapsto f_{\bf 0}(x,y)$$ is a partial computable function with the property that $\eta_x\simeq {\bf 0}$ iff $x\in K$. (I'm writing "$\simeq$," rather than "$=$," for equality of possibly-partial functions.)

The idea is then that our $h$ should be a function sending $x$ to an index for the partial computable function $\eta_x$. That is:

Suppose we have a total computable function $h$ such that for each $x$ we have $$\phi_{h(x)}\simeq \eta_x.$$ Then $h$ is an $m$-reduction of $K$ to $\{x: \phi_x\simeq {\bf 0}\}$.

The existence of such an $h$ is then justified by the s-m-n theorem, applied to the partial computable binary function $f_{\bf 0}$. So when the author more-or-less says "$f_{\bf 0}(x,y)$ demonstrates $K\le_m\{x: \phi_x\simeq {\bf 0}\}$," what they mean is that we can extract an appropriate reduction from $f_{\bf 0}$, not that $f_{\bf 0}$ is itself such a reduction.

  • $\begingroup$ Is this a good solution : i is such that f_i = 0 and j is such that f_j != 0. h(x) = i (if f_x (x)↓} and h(x) = j (else) ? $\endgroup$ – Paul Keseru Jan 21 at 19:45

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.