I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is not recognizable. Does anyone know how to do this reduction, what I come up with is:

Using python-like syntax:

def R(<M>,w):
    def F(x):
        if M(w)loops: //Run M on w
            return True on every x
            loop on every x
return F

Of course the problem here is that we can't really know when M loops on w

Does anyone know how to do this reduction, or if it is possible to prove that the language of TMs that accept every input string is unrecognizable using a reduction from a different unrecognizable language?

  • 2
    $\begingroup$ I am afraid that a TM that does not halt is not necessarily looping. That is true only of memory bounded automata. $\endgroup$
    – babou
    Commented Feb 22, 2015 at 10:20
  • 1
    $\begingroup$ @babou "Not halting" is often called "looping" even though the machine may move to new tape cells all the time. $\endgroup$
    – Raphael
    Commented Feb 22, 2015 at 11:07
  • 1
    $\begingroup$ Using closure properties is easier here. (What happens if a language and its complement are both recognizable?) $\endgroup$
    – Raphael
    Commented Feb 22, 2015 at 11:08
  • $\begingroup$ @Raphael Regarding "looping". I will take your word for it. But I will still consider it a poor practice as it may cause confusion between two very distinct concepts. $\endgroup$
    – babou
    Commented Feb 22, 2015 at 11:46
  • $\begingroup$ Hint: you are doing the reduction the wrong way around. Assume that your new language was semi-decidable and build a machine/algorithm for the complement of HALTING using it. $\endgroup$
    – Raphael
    Commented Feb 23, 2015 at 7:06

1 Answer 1



Let $H$ be the usual halting language: $$ H=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\} $$ Its complement is $$ \overline{H}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\} $$ We know that $H$ is recognizable (just run $M$ on $w$ and do what it does), so $\overline{H}$ must be unrecognizable (otherwise $H$ would be decidable, which we know isn't true).

The Reduction

As you suggested, we'll produce a reduction from $\overline{H}$ to $$ AH = \{\langle N\rangle\mid N \text{ halts on all }x\} $$ thus showing that $AH$ is unrecognizable. As you suggested, what we want is to map $(\langle M\rangle, w)$ to a description of a TM $M_w$ where

Mw(x) =
   run M on w
   if M(W) halts
   if M(w) doesn't halt

That would do it, except for the fact that if $M$ didn't halt on $w$, we'd never get to the $\texttt{halt}$ instruction. What we need is a finite way of testing for non-halting. A standard way to deal with this kind of difficulty is to limit the number of steps our simulation will perform, like this:

N(x) =
   run M on w for |x| steps
   if M has halted
   if M(w) hasn't halted yet

How does this modification help us?

  • If $(\langle M\rangle, w)\in\overline{H}$, then $M(w)$ will never halt, so $N(x)$ will halt after $|\,x\,|$ steps and thus $\langle N\rangle\in AH$
  • If $(\langle M\rangle, w)\notin\overline{H}$ then $M(w)$ will eventually halt, say after $s$ steps. This means that $N$ will halt on all inputs, $x$ of length less than $s$, and will loop on all longer inputs, so $\langle N\rangle\notin AH$.

This establishes the reduction we needed, and so we can conclude that $AH$ is non-recognizable.

  • $\begingroup$ I have an issue with this answer. What happens if $<M>$ is the Turing machine: Read all the input $x$, then do another step to the right, and then halt? On one hand, it will never halt after $|x|$ steps, therefore $N(x)$ will halt for all inputs, but $(<M>, x)\notin\overline{H}$ for any word $X$. $\endgroup$
    – Nescio
    Commented Jun 21, 2017 at 7:49
  • $\begingroup$ @Nescio For all words $x$ that are fed to $N$ by the supposed machine that recognizes AH, $M$ will be run on its own fixed word $w$. Think of $x$ not as a word, but as a counter which the machine $M$ cannot access. $\endgroup$ Commented Dec 14, 2017 at 14:52

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.