Consider a standard enumeration of Turing machines ($T_0, T_1, T_2$, ...).

Then, let language A be defined as $A = \{n \in\mathbb N | T_n(\lambda) \downarrow\}$.

I need to reduce it to the halting problem (let's call it $K$). So, I want $K \leq_m A$ (mapping reduction).

I know that mapping reduction is based on the idea that $w \in K$ if and only if $f(w) \in A$. Also, $f(w)$ must be computable. I don't know how to reduce properly.

  • $\begingroup$ Your question is quite unclear. Is $A$ the set of all Turing machines? Is it the set of Turing machines that always halt? Is it the set of Turing machines that halt when given themselves as input? It sounds like the first, but that's a decidable set. You can trivially reduce it to anything. $\endgroup$ – Sebastian Oberhoff Apr 2 '18 at 5:45
  • $\begingroup$ Can you show me how to formally reduce it to the halting problem set? I looked at some proofs online, but always stuck at proving that the function f(w) will be computable to correctly reduce the problem. Thanks!! $\endgroup$ – WOW Apr 2 '18 at 7:05
  • $\begingroup$ You say you want to reduce $A$ to $K$, then you write $K \leq_m A$, which instead mentions reducing $K$ to $A$, then you finally mention the definition, which is reducing $A$ to $K$ one again. Which direction are you trying to prove? $\endgroup$ – chi Apr 2 '18 at 7:51
  • $\begingroup$ Sorry again I started learning mapping reduction. I definitely meant K<A. So, reducing K to A. Thanks for editing. $\endgroup$ – WOW Apr 2 '18 at 7:53
  • $\begingroup$ $K\le_m A$ means $w\in K$ if and only if $f(w)\in A$. $\endgroup$ – xskxzr Apr 2 '18 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.