Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction from HALT to show that ALLHALT is not decidable.

Online (link) I found this (simular) solution:

$D$ = on input $s$:

  • Check that $s$ is of the form $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string over the input alphabet of $M$. If not, reject $s$. Otherwise continue.
  • Define a new machine $M_2$ corresponding to the pair $M, w$ as follows.

    $M_2$ = on input $v$:

    1. If $v$ is not the same as $w$, halt. Otherwise continue.
    2. Feed $v$ (meaning $w$ in this case) to $M$ and let $M$ compute on $w$.
    3. If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. If $M$'s computation on input $w$ halts and accepts $w$, halt. Otherwise continue looping like $M$ is doing.

Notice that we've designed $M_2$ in a clever way so that the result of $M$'s computation on input $w$ is encoded in the halting behavior of $M_2$. Namely, $M$ accepts $w$ if and only if $M_2$ halts on all inputs. In terms of language membership, this means that $\langle M, w\rangle$ belongs to Halt if and only if $\langle M_2\rangle$ belongs to Halt2. In light of this fact, finish the description of $D$'s computation as follows.

  • Feed the string $\langle M_2\rangle$ into the decider $D_2$.
  • Return $D_2$'s decision.

I don't understad the point 3: If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. Why does $M_2$ need to loop indefinitely?


1 Answer 1


Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:

\begin{align} \{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\ &\text{and $M$ }accepts\text{ $w$ after a finite computation}\} \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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