Examples of Many-one reductions.

Question

I'm trying to wrap my head around many-one reductions for an assignment in Mathematical Logic.

The assignment is to show

$A$ r.e $\Leftrightarrow$ $A\leq_m K$ where $K=\{x\in\mathbb{N}\ |\ x\in W_x\}$

($W_x$ is the domain of the (Turnip-)program having code $x$)

I don't want you to solve this explicitly but rather give examples of many-one reductions to help me reason about them. I've tried using Google for this but haven't found anything that helps me.

Can you give examples of recursively enumerable sets that easily can be reduced to K?

For reference:

$A\leq_m B$ iff there is a total recursive function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that $x\in A\Leftrightarrow f(x)\in B$

Answer 1

Well a standard r.e. set is $A=\{x:W_x\ne \emptyset\}$. For each $x$, we can define a function $$g_x(n)=\begin{cases} 0 &\text{if } (\exists m)[\varphi_x(m)\downarrow]\\ \uparrow &\text{otherwise} \end{cases}$$ and let $f$ be the function which takes $x$ to an index of $g_x$ (i.e. some $y$ such that $g_x=\varphi_y$).

Answer 2

Let $H = \{(e,x) : \Phi_e(x)\downarrow\} = \{(e,x) : x \in W_e\}$. $H$ is your standard Halting Problem set, which asserts that $(e,x) \in H$ if and only if the $e^\text{th}$ Turing program halts on input $x$.

A very useful fact is that $H \equiv_m K$, i.e. $H \leq_m K$ and $K \leq_m H$. It is clear that $K \leq_m H$. To show $H \leq_m K$, there exists a computable function $f$ such that $\Phi_{f(e,x)}(z)$ halts on any input $z$ if and only if $\Phi_e(x) \downarrow$. To precisely prove that $f$ is computable, you will likely need to use the s-m-n theorem. However appealing the Churing-Turing Thesis, given $e$, $x$, and $z$, make a program $\Psi$ such that $\Psi(e,x,z)$ halts if and only if $\Phi_e(x)\downarrow$ (note $z$ is not used at all). Because of the obvious uniformity (or use s-m-n theorem to be precise), there is a computable $f$ such that $\Psi(e,x,z) = \Phi_{f(e,x)}(z)$. Then $x \in H$ if and only if $\Phi_{f(e,x)}(f(e,x)) \downarrow$ if and only if $f(e,x) \in K$.

Hence this shows that $H \equiv_m K$.

Now to prove that $A$ is c.e. if and only if $A \leq_m K$. If $A$ is c.e., by definition $A = W_e = \text{dom}(\Phi_e)$ for some $e$. Hence $x \in W_e$ if and only if $(e,x) \in H$. Thus $A \leq_m H$ using the computable function $f(x) = (e,x)$. Since it was just shown that $H \leq_m K$, $A \leq_m K$ by transitivity of $\leq_m$. Suppose $A \leq_m K$. Then there is a computable function $f$ such that $x \in A$ if and only if $f(x) \in K$. Since $K$ is c.e., define

$\Psi(x) \begin{cases} 1 & \quad f(n) \in K \\ \uparrow & \quad \text{otherwise} \end{cases}$

is a partial computable function. hence $\Psi = \Phi_i$ for some $i$. Then $x \in A$ if and only if $\Psi(x) \downarrow$ if and only $x \in \text{dom}(\Phi_i)$ if and only if $x \in W_i$. Hence $A = W_i$. Thus $A$ is c.e.

---

This result shows that $K$ is $m$-complete, which is means every c.e. set is reducible to it. Another example, which is also a standard exercise in $m$-reducibility, is to show that $\{e : W_e \neq \emptyset\}$ is also $m$-equivalent to $K$.

An obvious example is $\emptyset \leq_m K$, but $K \not\leq_m \emptyset$.

---

$A \leq_m B$ means roughtly that there is a "very computable procedure" to determine membership in $A$ if you know about membership in $B$. So to solve reduciblity questions, you should think about how use $B$ to know about $A$, as in the example of obtaining above, where I reduced $H$ to $K$ and $K$ to $H$.

I say "very computable procedure" because there is a more general notion of Turing reducibility $A \leq_T B$, which more accurately means knowing $A$ computably from $B$.