6
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ Hi, Benjamin83, welcome to Math.SE! Thanks for bringing your questions here, hope you stay around and contribute to the site. $\endgroup$ – gt6989b Jun 17 '13 at 17:04
  • $\begingroup$ Miha Habič: they seem to be defined in the question already $\endgroup$ – Carl Mummert Jun 17 '13 at 19:05
  • $\begingroup$ @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 $\endgroup$ – Carl Mummert Jun 17 '13 at 19:06
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

In short, yes. In the special halting problem, you want to determine whether an arbitrary Turing machine with null input will halt or not, while with the general halting problem you want to know whether an arbitrary Turing machine with arbitrary input will halt or not. Clearly, since the special problem is a particular case of the general one, proving the general is sufficient to prove the special.

However, it's a lot harder to prove the general halting problem than the special one, hence why you tend to prove the special one, and from that prove the general one.

$\endgroup$
1
  • 3
    $\begingroup$ Strictly speaking, the special halting problem doesn't refer to giving a machine a null input but rather giving it its own index as input. It's a far less natural problem than the null-input version, and in fact it seems to be considered only because it makes the undecidability proof easier. $\endgroup$ – Andreas Blass Jun 17 '13 at 19:21

Your Answer

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

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