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?


closed as off-topic by Sasho Nikolov, Emil Jeřábek supports Monica, Jan Johannsen, Kaveh, Hsien-Chih Chang 張顯之 Jun 28 '17 at 18:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Sasho Nikolov, Emil Jeřábek supports Monica, Jan Johannsen, Kaveh, Hsien-Chih Chang 張顯之
If this question can be reworded to fit the rules in the help center, please edit the question.


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

  • $\begingroup$ Thanks for the intelligently written explanation yes now I'm good $\endgroup$ – user1993748 Jun 26 '17 at 19:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.