# Undecidability of the halting problem

One can prove by reduction from the special halting problem $H_S$ the undecidability of the (general) halting problem $H$. Is the converse also possible? That is, is it possible to prove the undecidability of the special halting problem $H_S$ by reduction from the (general) halting problem $H$?

The language $H_S$ of the special halting problem:

$H_S := \{w: w \mbox{ encodes a Turing machine }M_w \mbox{ and } M_w \mbox{ accepts } w \}$

The language $H$ of the (general) halting problem:

$H:=\{\langle w,x\rangle\;:\;w \mbox{ encodes a Turing machine }M_w \mbox{ and } M_w \mbox{ accepts } x\}$

In both definitions $w,x\in \Sigma^*$ for some alphabet $\Sigma$.

• Hi, Benjamin83, welcome to Math.SE! Thanks for bringing your questions here, hope you stay around and contribute to the site. – gt6989b Jun 17 '13 at 17:04
• Miha Habič: they seem to be defined in the question already – Carl Mummert Jun 17 '13 at 19:05
• @Benjamin83: general questions about computability should be tagged as "computability". This question is purely mathematical, so the "computer science" tag is unnecessary, and this question has nothing to do with computational complexity – Carl Mummert Jun 17 '13 at 19:06

Here is how to reduce the general problem to the special one. Given a machine $w$ and input $x$, apply the s-m-n theorem to obtain a machine $w'$ which, regardless of its input, simulates the execution of machine $w$ with input $x$. Then $w' \in H_S$ if and only if $\langle w,x\rangle \in H$.
The opposite reduction is trivial: $w \in H_S$ if and only if $\langle w,w\rangle \in H$.