<p>Note that any computable language $L$ can be turing-reduced to any other language $L'$ which contains at least one yes-instance and one no-instance (i.e. we have $L \leq L'$) by letting the reduction mapping do all the computation and then mapping to a yes-instance of $L'$ if the original instance is in $L$ or a no-instance of $L'$ if it is not, so naturally a decidable language like $\mathcal{E}^\ast$ can be reduced to the halting problem.</p>

<p>However, we cannot reduce the halting problem $\text{HP}$ to $\mathcal{E}^\ast$ as $\mathcal{E}^\ast$ (assuming that your alphabet is $\{0,1\}$) contains every possible input and thus has no no-instance. Therefore it is not possible to find a function that maps the no-instances of $\text{HP}$ to the no-instances of $\mathcal{E}^\ast$ as there are none (or more differently: since $\mathcal{E}^\ast$ is decidable, we cannot reduce $\text{HP}$ to it as it is undecidable and the existence of a reduction would contradict that -- can you see why?)</p>

CC BY-SA 3.0
2017-06-26T19:23:59.913Z
Thanks for the intelligently written explanation yes now I'm good
Waseem Francis
CC BY-SA 3.0
2017-06-26T12:23:44.220Z
2017-06-26T12:23:44.220Z
Watercrystal
<p>I'm studying Theory Of Computation and have some questions in the beginning: </p>

<p>About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$</p>

<p>$HP =$ {$&lt;M,w&gt;$ $|$ $M$ is a $TM$ and it halts on string $w$}.</p>

<p>$\mathcal{E} =$ {$0$,$1$} </p>

<p>why this is true : $\mathcal{E}\mbox{*} \leq HP$</p>

<p>but this is not true : 
$HP\leq\mathcal{E}\mbox{*}$</p>

<p>I have read that <strong>IF</strong> the second argument is true then we get that : 
$HP$ $\epsilon $ $   R$ which I know that it is not true.</p>

<p>I'm new to this topic could someone give an explination on these points?</p>

<cc.complexity-theory><reductions><universal-turing-machines>
About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$
Waseem Francis
# About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$

(Asked by: username_0 on 2017-06-26)

I'm studying Theory Of Computation and have some questions in the beginning:

About reduction relation between $HP$ and $\mathcal{E}\mbox{\*}$

$HP =$ {$$ $|$ $M$ is a $TM$ and it halts on string $w$}.

$\mathcal{E} =$ {$0$,$1$}

why this is true : $\mathcal{E}\mbox{\*} \leq HP$

but this is not true :
$HP\leq\mathcal{E}\mbox{\*}$

I have read that **IF** the second argument is true then we get that :
$HP$ $\epsilon $ $ R$ which I know that it is not true.

I'm new to this topic could someone give an explination on these points?

**Tags:** cc.complexity-theory, reductions, universal-turing-machines


---

## 1 answers

### Answer by username_1 on 2017-06-26. Score: 1 | Accepted answer

Note that any computable language $L$ can be turing-reduced to any other language $L'$ which contains at least one yes-instance and one no-instance (i.e. we have $L \leq L'$) by letting the reduction mapping do all the computation and then mapping to a yes-instance of $L'$ if the original instance is in $L$ or a no-instance of $L'$ if it is not, so naturally a decidable language like $\mathcal{E}^\ast$ can be reduced to the halting problem.

However, we cannot reduce the halting problem $\text{HP}$ to $\mathcal{E}^\ast$ as $\mathcal{E}^\ast$ (assuming that your alphabet is $\{0,1\}$) contains every possible input and thus has no no-instance. Therefore it is not possible to find a function that maps the no-instances of $\text{HP}$ to the no-instances of $\mathcal{E}^\ast$ as there are none (or more differently: since $\mathcal{E}^\ast$ is decidable, we cannot reduce $\text{HP}$ to it as it is undecidable and the existence of a reduction would contradict that -- can you see why?)

> **Comments:**
> **username_0**: Thanks for the intelligently written explanation yes now I'm good  

---

