Many-one Reduction of $K_0$ to $K$

463 Views Asked by At

I was recently studying some computability theory and stumbled upon the concept of many-one reducibility and creative sets. We have the following definitions

$$ \begin{align*} K &= \{x : x \in W_x\} \\ K_0 &= \{\left< x , y \right>\ : x \in W_y\} \\ \end{align*} $$

I am trying to show that $K_0 \equiv_m K$ and got stuck on the part where I need to prove that $K_0 \leq_m K$ (i.e $K_0$ is many-one reducible to $K$). Intuitively this seems difficult since $K_0$ seems to have "more" information than $K$. I had thoughts of using the $s^n_m$ or fixed point theorems but didn't get anywhere. I would appreciate any guidance with this.

Here is what I tried doing:

We know

$$ \begin{align*} \left<x,y\right> \in K_0 &\iff x \in W_y \\ \end{align*} $$

or in other words, if $\varphi_y(x) \downarrow$. We can instead look at some machine with function $\varphi_e(y, x, z)$ that takes three parameters and simulates running input $x$ on machine $y$ and $z$ is just a dummy variable that gets cleared from the tape. Then by the s-m-n theorem, there is some computable function $S^1_1$ s.t $\varphi_{S^1_1(e, y, x)}(z) = \varphi_e(y,x,z)$. Then we have:

$$ \begin{align*} \left<x,y\right> \in K_0 &\iff x \in W_y \\ &\iff \varphi_{S^1_1(e,y,x)}(z) \downarrow \text{ for any } z \\ &\iff \varphi_{S^1_1(e,y,x)}(S^1_1(e,y,x)) \downarrow \\ &\iff S^1_1(e,y,x) \in W_{S^1_1(e,y,x)} \\ &\iff S^1_1(e,y,x) \in K \\ \end{align*} $$

and so in summary

$$ \begin{align*} \left<x,y\right> \in K_0 &\iff S^1_1(e,y,x) \in K \end{align*} $$

where $S^1_1$ is computable so this gives $K_0 \leq_m K$.

Is this proof valid or have I messed something up?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, this proof seems basically fine. Given $x$ and $y$ you can effectively construct an index $z = f(x,y)$ so that if $x \in W_y$ then $W_z = \mathbb{N}$ and $W_z = \emptyset$ otherwise. Then we have $z \in W_z$ if and only if $x \in W_y$. So $f$ is a many-one reduction from $K_0$ to $K$.