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

Question

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

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

$HP =$ {$<M,w>$ $|$ $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?

Answer 1

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?)