# M-reducable set

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?

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.

• 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) ? – Paul Keseru Jan 21 at 19:45