2

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$

Hashmush
  • 153
  • 2
    Presumably, the spelling corrector changed Turing to turnip... – Thomas Andrews Jan 05 '13 at 22:36
  • @ThomasAndrews Nope, it is actually the correct one. I have only seen it in my course book though http://www.oup.com/us/catalog/general/subject/Mathematics/Logic/~~/dmlldz11c2EmY2k9OTc4MDE5ODUyOTgwNA==

    One defines $T^{++}$-programs on Turnip machines. It's kinda silly.

     – Hashmush Jan 05 '13 at 23:16
  • Ah, it's probably using something different enough from Turing machines to make the Johor want to avoid using that name – Thomas Andrews Jan 05 '13 at 23:21
  • The way I think about $A \leq_{m} B$ is that we can determine if $a \in A$ (or not) by asking a single, effectively determinable question about $B$. So if we have knowledge of $B$ (i.e. you can always tell if $b\in B$), the we also have knowledge of $A$ (since we have access to $f$). This is a way of describing the idea that $A$ can be computed from $B$, though, as @William indicated, this is not the most general way since a single pre-specified question about $B$ is too stringent. – Quinn Culver Jan 06 '13 at 20:24

2 Answers2

2

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$).

Alex Becker
  • 60,569
  • Thank you! It's so simple as soon as you understand how it works. On question though: Why is $f$ recursive? I'm guessing that I'm missing some simple fact about it. – Hashmush Jan 06 '13 at 11:58
  • @Hashmush Well $f(x)$ is just the Godel number (or whatever enumeration you choose) of $g_x$, and the definition I've given can be turned into a Godel number by some standard algorithm (the algorithm being independent of $x$), after you replace $\varphi_x$ with the symbols defining $\varphi_x$. – Alex Becker Jan 06 '13 at 15:44
  • @Hashmush He's employing the Church-Turing thesis to conclude $f$ is computable (because proving it rigorously would very tedious). – Quinn Culver Jan 06 '13 at 20:17
1

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$.

William
  • 19,935